UVa 1644 - Prime Gap（筛选求素数）

发表于 分类于 ， Disqus：

求给出的数最近的两个素数的差，若给的数是素数，输出0。

在青岛理工大学邀请赛时，做过这道题，当时打表打在循环内了，超时了。这个问题一定要注意。

再说这个求素数，之前OJ作业上做到过筛选求素数的题，后来百度过高速求素数的方法，XA2的Xcode 5亿素数5秒左右，具体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
const unsigned maxn=1300010;
int p[maxn],n;
bool np[maxn]={true,true};
int main(){
    ios::sync_with_stdio(false);
    for(int i=2;i<maxn;i++){
        if(!np[i])
            p[n++]=i;
        for(int j=0;j<n&&i*p[j]<maxn;j++){
            np[i*p[j]]=1;
            if(!(i%p[j])) break;
        }
    }
    while(cin>>n&&n){
        if(!np[n]){
            cout<<"0"<<endl;
            continue;
        }
        int i=n,j=n;
        while(np[i]) i--;
        while(np[j]) j++;
        cout<<j-i<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章