质数距离

素数距离
给定两个整数l，u求l到u之间相邻两个质数的差最大是多少。
数据范围（1 <= L <U <= 2,147,483,647）L和U之差不超过1,000,000。

试除法优化

算法分析：这道题涉及到了如何快速判断质数，使用试除法时间太慢肯定超时。有一种对试除法的优化，线筛求出1~ $\sqrt n$ 之间的质数，对n尝试除以1~ $\sqrt n$ 之间的质数。如果n是合数那么一定能被整除。1~n之间大概有 $\frac n {\ln n}$ 个质数。可以估计时间复杂度是 $O((U-L)*\frac {\sqrt U} {\ln {\sqrt U} })$ ,当u为1e9左右时，这个算法比没有优化的快10倍。

倍数法筛质数

对于区间[l,r]我们只要能够找到一个x，x是p的倍数。那么说明x是合数，x+p是合数，x-p也是合数。这样对每个质数来说，我们就可以 $O(U-L)/p$ 的时间筛完p的倍数。
扫描1到 $\sqrt u$ 之间的所有质数p，我们标记所有 $i*p,(\lceil \frac L P \rceil \leq i \leq \lfloor \frac U P \rfloor)$ 为合数即可。其中每个合数只会被他不同的质因数筛一遍，这就是埃筛的时间复杂度，十分接近线性。
有一点非常有趣就是向上取整和向下取整的实现方法。c++的整除除法就是向下取整，向上取整给分子加上分母-1就可以了。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<long long> p;
bool v[50010];
void get_prime(){
    for(int i = 2;i<=50000;i++){
        if(v[i]==0)p.push_back(i);
        for(int j = 0;p[j]*i<=50000;j++){
            v[i*p[j]] = 1;
            if(i%p[j]==0)break;
        }
    }
}
bool is[1000010];
int main(){
    get_prime();
    int l,r;
    while(cin>>l>>r){
        memset(is,0,sizeof is);
        for(int i = 0;p[i]<=r/p[i];i++){
            for(int j = ((l+p[i]-1)/p[i]);j<=r/p[i];j++){
                if(j!=1){ 
                    is[j*p[i] - l] = 1;    
                }
            }
        }
        int last=-1,p1,p2,dis=0,p3,p4,dis1=0x3f3f3f3f;
        for(int i = 0;i<=r-l;i++){
            if(i+l<=1)continue;//特判0和1
            if(!is[i]){
                if(last!=-1&&i-last > dis){
                    p1 = last ,p2 = i;
                    dis = p2 - p1;
                }
                if(last!=-1&&i-last < dis1){
                    p3 = last ,p4 = i;
                    dis1 = p4 - p3;
                }
                last = i;
            }    
        }
        if(dis!=0&&dis1!=0x3f3f3f3f){
            cout<<p3+l<<","<<p4+l<<" are closest, "<<p1+l<<","<<p2+l<<" are most distant."<<endl;
        }
        else cout<<"There are no adjacent primes."<<endl;
    }
}

最后编辑于：2020.08.04 22:19:24