【POJ 2689】 Prime Distance

【题目链接】

             http://poj.org/problem?id=2689

【算法】

           我们知道，一个在区间[l,r]中的合数的最小质因子必然不超过sqrt(r)

           那么，先暴力筛出1-50000中的质数，对于每个询问，用筛出的质数标记[l,r]中的合数，即可

【代码】

            

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include <set>  
#include   
#include   
#include   
#include <string>  
#include   
#include   
#include   
#include   
#include   
#include  
using namespace std;
#define MAXP 50000
#define MAXD 1000010
const int INF = 2e9;

int i,j,last,mx,mn,l,r,L,U;
vector<int> P;
bool not_prime[MAXD];
pair<int,int> C,D;
bool flag;

inline void init()
{
        int i,j,tmp;
        static int f[MAXP+1];
        for (i = 2; i <= MAXP; i++)
        {
                if (!f[i])
                {
                        P.push_back(i);
                        f[i] = i;
                }
                for (j = 0; j < P.size(); j++)
                {
                        tmp = i * P[j];
                        if (tmp > MAXP) break;
                        f[tmp] = P[j];
                        if (f[i] == P[j]) break;
                }
        }        
}

int main() {
        
        init();
        while (scanf("%d%d",&L,&U) != EOF)
        {
                memset(not_prime,false,sizeof(not_prime));
                flag = false;
                last = -1;
                mx = 0; mn = INF;
                for (i = 0; i < P.size(); i++)
                {
                        if (L % P[i] == 0) l = L / P[i];
                        else l = L / P[i] + 1;
                        r = U / P[i];
                        for (j = max(l,2); j <= r; j++) not_prime[P[i]*j-L] = true; 
                }
                if (L == 1) not_prime[0] = true; 
                for (i = 0; i <= U - L; i++)
                {
                        if (!not_prime[i])
                        {
                                if (last == -1) 
                                {
                                        last = i;
                                        continue;
                                }
                                if (i - last < mn)
                                {
                                        flag = true;
                                        mn = i - last;
                                        C = make_pair(last+L,i+L);
                                }
                                if (i - last > mx) 
                                {
                                        flag = true;
                                        mx = i - last;
                                        D = make_pair(last+L,i+L);        
                                }        
                                last = i;
                        }        
                }
                if (flag) printf("%d,%d are closest, %d,%d are most distant.\n",C.first,C.second,D.first,D.second);
                else printf("There are no adjacent primes.\n");
        }
        
        return 0;
    
}
数学

相关

Liquidity Providers 的数学原理

『笔记』组合数学

组合数学练习

【YBTOJ高效进阶 21190】欧拉函数（数学）

北京市第14届大学生数学竞赛本科甲乙组试题及参考解答 北京市第14届大学生数学竞赛本

洛谷 P3711 - 仓鼠的数学题（多项式）

结对编程项目总结-带UI的小初高数学学习软件

大数据数学基础--用python实现微积分 20212311孙佳瑜

【数学】卢卡斯定理

数学软件

数学软件

[总结]多项式类数学相关（定理&证明&板子）

标签