介绍

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;        }}

对应题目：

对应题目代码：

#include
    
     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;            }        }    }}