Eratosthenes筛法,又名埃氏筛法,对于求1~n区间内的素数,时间复杂度为n log n,对于10^6^ 以内的数比较合适,再超出此范围的就不建议用该方法了。 筛法的思想特别简单: 对于不超过n的每个非负整数p, 删除2p, 3p, 4p,…, 当处理完所有数之后, 还没有被删除的就是素数。
void init()
{
int cnt=0;
for(int i=0;i <= Max;i++)
is_prime[i] = true;
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=Max;i++)
if(is_prime[i])
{
prime[cnt++]=i; //边筛边记录素数
for(int j=2*i;j<=Max;j+=i)
is_prime[j]=false;
}
}
对应题目:Prime Gap UVA - 1644 对应题目代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
const int maxn = 100001, Max = 1299721;
int prime[maxn];
bool is_prime[Max+1];
void init()
{
int cnt=0;
for(int i=0;i <= Max;i++)
is_prime[i] = true;
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=Max;i++)
if(is_prime[i])
{
prime[cnt++]=i; //边筛边记录素数
for(int j=2*i;j<=Max;j+=i)
is_prime[j]=false;
}
}
int main()
{
std::ios::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
init();
while(cin >> n && n)
{
if(is_prime[n])
{
cout << 0 << endl;
continue;
}
for(LL i = 0; i < maxn; i++)
{
if(prime[i] > n)
{
if(prime[i] != n)
cout << prime[i] - prime[i-1] << endl;
break;
}
}
}
}