1.朴素版的筛法 O（nlogn）

每次循环筛掉ii的倍数

题目：httpss://www.acwing.com/problem/content/870/

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

using namespace std;
const int N = 1000010;
int n;
int cnt;
bool st[N];
void get_prime()
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i]) cnt ++;
		
		for (int j = i + i; j <= n; j+=i) st[j] = true;
	}
}

int main()
{
	scanf("%d", &n);
	get_prime();
	printf("%d", cnt);
}

2.埃氏筛法 O（nloglogn）

在上面的代码中在每次判断中我们都执行了forfor循环来筛掉ii的倍数， 但是是可以优化的，我们将forfor循环放进ifif判断里面，这样当ii已经被筛掉时，就不用重复的筛选了，成功降低时间复杂度。

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

using namespace std;
const int N = 1000010;
int n;
int cnt;
bool st[N];
void get_prime()
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])
		{ 
		    cnt ++;
            // 放进判断里面循环。
		    for (int j = i + i; j <= n; j+=i) st[j] = true;
		}
	}
}

int main()
{
	scanf("%d", &n);
	get_prime();
	printf("%d", cnt);
}

3.线性筛法O(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
32
33
34
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1000010;
int n;
int primes[N];
int cnt;
bool st[N];
void get_prime()
{
    for (int i = 2; i <= n; i++)
	{
        if (!st[i]) primes[cnt++] = i;
        //n只会被最小质因子筛掉，6会被2筛选，9会被3筛选
        //不需要考虑primes*i大于n的数
        //筛去合数
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[i * primes[j]] = true;
            // 表示已经筛选过了,已经找到了该值的最小质因数
            //prime[j]一定是i*primes[j]的最小质因子,prime从小到大存放的素数
            // i%primes[j] != 0 , primes[j] 一定小于i的所有因子,prime[j]一定是i*primes[j]的最小质因子
            if (i%primes[j] == 0) break;
        }
    }
}

int main()
{
    scanf("%d", &n);
    get_prime();
    printf("%d", cnt);
}