加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

[POJ2689]Prime Distance

发布时间:2020-12-14 04:24:46 所属栏目:大数据 来源:网络整理
导读:题目:Prime Distance 传送门:http://poj.org/problem?id=2689 分析: 1. $ [L,R] $ 只有1e6,于是暴力写了个millRabin测试,时间复杂度大约$ O(N*k*logN) $然后Tle。 2. 可以考虑一下二次筛法。$ [L,R] $ 中每一个合数一定包含一个不超过$ sqrt n $ 的质

题目:Prime Distance

传送门:http://poj.org/problem?id=2689

分析:

1. $ [L,R] $ 只有1e6,于是暴力写了个millRabin测试,时间复杂度大约$ O(N*k*logN) $然后Tle。

2. 可以考虑一下二次筛法。$ [L,R] $ 中每一个合数一定包含一个不超过$ sqrt n $ 的质因子。

3. 我们把$ [ 1,sqrt R ] $ 的质数筛出来。

4. 再标记 $ i*p,i in [ [frac{L}{p}],[frac{R}{p}] ] $,就是把$ [L,R] $之间的合数筛掉。这个常数很小,时间复杂度$ O(sum{frac{R-L}{p}}) $ 。?

5. 剩下的就是质数啦。

?

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF=1<<30,maxN=50005;
int pn,p[maxN],vis[1000007];
void getPrime(){
    for(int i=2;i<maxN;++i){
        if(!vis[i])p[++pn]=i;
        for(int j=1;j<=pn && i*p[j]<maxN;++j){
            vis[i*p[j]]=true;
            if(i%p[j]==0)break;
        }
    }
}
void getPrimeInLR(const int &L,const int &R){
    memset(vis,0,sizeof(vis));int *use=vis-L;
    for(int i=1,sR=sqrt(R+0.5);i<=pn && p[i]<=sR;++i){
        int k=ceil((double)L/p[i]);if(k<=1)++k;
        for(int j=(LL)k*p[i];j>0 && j<=(LL)R;j+=p[i])use[j]=1;
    }
    if(L==1)vis[0]=1;
}
int main(){
    getPrime();
    for(int L,R;~scanf("%d%d",&L,&R);){
        int i=L,last=0,*use=vis-L;int mn0=0,mn1=INF,mx0=0,mx1=0;
        getPrimeInLR(L,R);
        for(;i<=R && !last;++i)if(!use[i])last=i;
        for(;i>0 && i<=R;++i)
            if(!use[i]){
                if(i-last<mn1-mn0){mn1=i;mn0=last;}
                if(i-last>mx1-mx0){mx1=i;mx0=last;}
                last=i;
            }
        if(!mn0)puts("There are no adjacent primes.");
        else printf("%d,%d are closest,%d,%d are most distant.n",mn0,mn1,mx0,mx1);
    }
    return 0;
}

?

素数筛的常数计算:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF=1<<30,vis[1000007];
void getPrime(){
    for(int i=2;i<maxN;++i){
        if(!vis[i])p[++pn]=i;
        for(int j=1;j<=pn && i*p[j]<maxN;++j){
            vis[i*p[j]]=true;
            if(i%p[j]==0)break;
        }
    }
}
int main(){
    double ans=0;
    getPrime();
    for(int i=1;i<pn;++i)
        printf("%d %lfn",i,ans+=1.0/p[i]);
    return 0;
}
View Code

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读