Get Primes

筛质数

分析

定义全局变量：
- primes[N]：存储所有筛出的质数
- st[N]：标记每个数是否为合数（true 表示不是质数）
- cnt：统计质数数量
线性筛法（每个合数只会被它的最小质因子筛去一次）
- 遍历 i 从 2 到 n
- 如果 st[i] == false，说明 i 是质数，记录到 primes[cnt ++ ]
- 枚举当前已记录的质数 primes[j]
  - 将 primes[j] * i 标记为合数
  - 如果 i % primes[j] == 0，说明 primes[j] 是 i 的最小质因子，直接 break，防止重复标记
    - primes[j] 是 i 的最小质因子
    - 那么 primes[j] * i 的最小质因子仍然是 primes[j]
    - 如果继续用后面的 primes[k] 去乘 i，生成的 primes[k] * i 这个合数，其最小质因子可能不是 primes[k]，而是 primes[j]，违背线性筛只由最小质因子筛的原则

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度 O(n)

C++代码

 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


#include <iostream>

const int N = 1000010;
int primes[N];  // 存储所有质数
bool st[N];     // st[i] 为 true 表示 i 是合数
int cnt = 0;    // 质数个数

void get_primes(int n)
{
  for (int i = 2; i <= n; ++ i)
  {
    if (!st[i])
      primes[cnt ++ ] = i;  // i 是质数，存入 primes
    for (int j = 0; primes[j] * i <= n; ++ j)
    {
      st[primes[j] * i] = true;  // 用质数 primes[j] 筛掉 i 的倍数
      if (i % primes[j] == 0) break;  // primes[j] 是 i 的最小质因子，跳出
    }
  }
}

int main()
{
  int n;
  std::cin >> n;

  get_primes(n);  // 筛出所有小于等于 n 的质数

  std::cout << cnt << '\n';  // 输出质数个数

  return 0;
}