868.质数筛

时/空限制：0.2s / 64MB

题目描述

给定一个正整数 \(n\)，请你求出 \(1 \sim n\) 中质数的个数。

输入格式

共一行，包含整数 \(n\)。

输出格式

共一行，包含一个整数，表示 \(1 \sim n\) 中质数的个数。

数据范围

\(1 \le n \le 10^6\)

输入样例

8

输出样例

4

解释：输入 \(8\)，则 \(8\) 以内有 \(4\) 个质数，分别为 \(2\)、\(3\)、\(5\)、\(7\)。

代码

筛质数：先去掉 \(2\) 的倍数，再去掉 \(3\) 的倍数，再去掉 \(4\) 的倍数，…依此类推，最后剩下的就是素数。

primes数组存放的是 \(1 \sim n\) 中的质数。cnt只是一个索引，st数组用来标记对应索引是否筛掉，初始默认false。

埃氏筛法

思路是，每次遍历找出一个数，第一次筛出来的 \(2\) 肯定是质数，将 \(2\) 加入到primes数组中，然后成倍增加其值，\(2\) 的倍数都不是质数，直接筛除掉，然后继续筛 \(3\)，将 \(3\) 加入到primes数组中，依次遍历下去，最后始终筛不出来的一定是质数。

const int N = 1000010;

int primes[N], cnt;	// primes数组存储所有质数
bool st[N];			// 初始化为false，st数组标记被筛掉的索引

// 暴力做法O(n log(logn)) 埃氏筛法
void get_primes(int n) {
    for(int i = 2; i <= n; ++i) {
        if(!st[i]) primes[cnt++] = i;	// 记录筛出的质数
        for(int j = 2*i; j <= n; j += i) st[j] = true;
    }
}

欧拉筛法（线性筛法）

核心思想：每个合数必有一个最小质因数，用这个最小的质因数筛掉合数。

const int N = 1000010;

int primes[N], cnt;
bool st[N];

// 线性O(n)优化 欧拉筛法
void get_primes(int n) {
    for(int i = 2; i <= n; ++i) {
        if(!st[i]) primes[cnt++] = i;		// 没有被筛去 说明是质数
        for(int j = 0; primes[j] <= n/i; ++j) {
            st[primes[j] * i] = true;       // 用最小质因子去筛合数primes[j] * i
            if(i % primes[j] == 0) break;   // 当该条件成立 primes[j]一定是i的最小质因子
        }
    }
}

理解：

• 当i % primes[j] != 0时，说明此时遍历到的primes[j]不是i的质因子，那么此时的primes[j]一定小于所有i的质因子，但是能说明：
  • primes[j] * i的最小质因子是primes[j]」
• 当有i % primes[j] == 0时，说明i的最小质因子是primes[j]，因此能说明：
  • primes[j] * i的最小质因子也就应该是prime[j]

综上两种情况，不论是什么情况，都可以得出结论：primes[j] * i的最小质因子是primes[j]。

所以上述代码中第二层for循环里，无论什么情况，primes[j]都是primes[j] * i的最小质因子，所以在枚举时都会执行语句：

st[primes[j] * i] = true;

来通过当前primes[j] * i的最小质因子primes[j]去把primes[j] * i删除掉。

总之，对于一个合数x，假设primes[j]是x的最小质因子，当i枚举到x / primes[j]时，一定能够把对应的合数x筛掉。

注意

• 在第二层for循环中，判断条件不必写为：for(int j = 0; j < cnt && primes[j] <= n/i; ++j)，原因有两点：
  • 若i为合数，当primes[j]枚举到i的最小质因子时，就一定会通过break语句跳出循环。
  • 若i为质数，当primes[j]遍历到primes[j] = i时也会通过break语句跳出循环。
  • 所以综上两点原因，一定会在cnt之前就停下来，所以j < cnt这条语句是不需要添加的。
• 线性筛法保证了所有的合数都是被它的最小质因子筛掉的。