埃氏筛法（埃拉托斯特尼筛法）

发表于 更新于 分类于 ，
本文字数： 798

求n以内质数，筛掉不大于根号n的所有质数的倍数（合数）

《算法竞赛 入门到进阶》给的模板 ：

1
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
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, cnt = 0, primes[N];

bool st[N];

int main()
{
    cin >> n;
    for (int i = 2; i * i <= n; i++)
    {
        if (!st[i])
        {
            for (int j = i * i; j <= n; j += i) //优化为i^2 以5为例5*2 5*3 5*4已经在i=2和3时筛掉了
                st[j] = true;
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[++cnt] = i;
        }
    }
    cout << cnt;
    return 0;
}

合并一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, cnt = 0, primes[N];

bool st[N];

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[++cnt]=i;
            for (long long j = (long long int)i * (long long int)i; j <= n; j += i)
                st[j] = true;
        }
    }
    cout << cnt;
    return 0;
}

时间复杂度：O(nloglogn)