素數篩法（Eratosthenes篩法）

介紹

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

}