埃氏筛法

· · 个人记录

质数筛法有很多种，这里介绍最简单的一种,埃氏筛法。

一个数如果它有除 1 和自己以外的约数，那么它一定不是一个质数，因此考虑枚举 1−>N ​​ 中每个数的倍数，并标记它们。这些被标记的就一定不是质数了，相反，剩下那些没有被标记的，就是我们“筛选”出来的质数。

以 n=50 为例：先假设 [2,n] 所有数都是质数。

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,28,29,30,

31,32,33,34,35,36,37,38,39,40,

41,42,43,44,45,46,47,48,49,50

大于 2 ​ 的 2 ​ 的倍数一定不是质数，标记 4,6,8...50 ​。

大于 3 ​​ 的 3 ​​ 的倍数一定不是质数，标记 6,9,12...48 。​

大于 5 的 5 的倍数一定不是质数，标记 10,15...50 。

大于 7 的 7 的倍数一定不是质数，标记 14,21...49 。

一直这样下去， 最终留下来未被标记的就都是质数了。

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47。

可以结合下面这两张动图理解：

你会计算这个算法的复杂度吗？

循环的总次数小于：

n/1+n/2+n/3+....n/n

根据欧拉1734年得到的结论：

11+12+13+...1n=ln(n+1)+γ

整个算法的复杂度为 O(nlog(n)) ，其中 γ≈0.577218 ，也被称为欧拉常数。

当范围在int范围内：

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn=5000000;
long prime[maxn];    // 存储一个个确定为质数的数
bool is_prime[maxn+1];    // 标记范围内所有数
int p = 0;
int sieve(int n)
{
    p = 0;
    for(int i=0;i<=n;i++)
        is_prime[i]=true;       // 所有数先标记为true
    is_prime[0] = is_prime[1] = false;   // 把数字0，1标记为质数
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])         // 如果这个数没有被标记为false
        {
             prime[p++]=i;       // 用prime数组存起来这个数，既存起了质数，又用p表示了质数个数
             for(int j=i*i;j<=n;j+=i)   // 这里没有优化时的写法是for(int j=2*i; j<=n; j++)。
            //因为小于j(即i^2)内的合数都因为(根号j)(即i)内有更小的j的的因数而被排除
                                // 比如3^2 = 9，为什么不算2*3 = 6呢， 因为6<9,所以6因为3以内有更小的因数而直接被排除
                    is_prime[j]=false;
        }
    }
    return p;          // 返回质数个数
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        printf("质数个数是: %d\n",sieve(n));
        printf("质数有:\n");
        for (int i = 0; i<p; i++)
        {
            printf("%d ", prime[i]);
            printf("\n\n");
        }
    }
    system("pause");
}

当范围超过了int

static const int N = 1e7;
bool is_prime[N];   // 判断是否是素数
ll prime[N];       // 存储素数
ll sieve(ll num)
{
    int inx = 0;
    for (int i = 0; i<=N; i++)
        is_prime[i] = true;

    is_prime[0] = is_prime[1] = false;

    int MIN = (num > N) ? N : num;

    for (ll i = 2; i<=MIN; i++)
    {
        if (is_prime[i])
        {
            prime[inx++] = i;

            for (ll j = i*i; j<=num; j+=i)
                is_prime[j] = false;
        }
    }
    return inx;
}

int gcd(int inx)    // 此处由于传进来都是质数，所以直接相乘即为gcd
{
    int res = 1;
    for (int i = 0; i<inx-1; i++)
        res *= prime[i];
    return res;
}

void C3()
{
    ll num;     // 输入数
    int p;       // 最小公约数

    cin >> num;

    int inx = sieve(num);   // 筛选素数

    cout << gcd(inx) << endl;
}

建议做题 ：

质数中的质数（质数筛法）

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。

输入格式

输入一个数N(N <= 10^6)

输出格式

输出>=N的最小的质数中的质数。

输入样例

20

输出样例

31

此题使用埃氏筛法

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool f[1001001];
int prime[80000], cnt = 0;

void sieve(int x) {
    for (int i = 2; i <= x; ++i) {
        if (!f[i]) {
            prime[cnt++] = i;
            for (ll j = (ll)i * i; j <= x; j += i)
                f[j] = 1;
        }
    }
}

int main() {
    int  n, pos;
    cin >> n;
    sieve(n + 1000);
    pos = upper_bound(prime, prime + cnt, n - 1) - prime;
    pos = upper_bound(prime, prime + cnt, pos) - prime;
    cout << prime[prime[pos] - 1] << endl;
    return 0;
}

████████████████████████████████████████████████