素数筛法（Eratosthenes筛法）

介绍

Eratosthenes筛法，又名埃氏筛法，对于求1~n区间内的素数，时间复杂度为n log n，对于10⁶ 以内的数比较合适，再超出此范围的就不建议用该方法了。

筛法的思想特别简单：对于不超过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;

            }

        }

    }

}

巴特西

素数筛法（Eratosthenes筛法）

介绍

代码

最新文章

热门文章