欧拉筛法（线性筛）

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

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

using namespace std;

const int N = 1e8 + 10;

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

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (!primes[i])
            primes[++cnt] = i;
        for (int j = 1; i * primes[j] <= n; j++)
        {
            primes[i * primes[j]] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
    for (int j = 1; j <= cnt; j++)
    {
        cout << primes[j] << " ";
    }
    cout << endl << cnt;
    return 0;
}

分析：

  1. i % primes[j] == 0 时，primes[j] 是 i 的最小质因子，所以 primes[j] 也是 i * primes[j] 的最小质因子
  2. i % primes[j] != 0 时 ，primes[j] 小于 i 的所有质因子，所以 primes[j] 也是 i * primes[j] 的最小质因子
  3. 对于任意合数 x ，假设 primes[j] 为 x 的最小值因子，当枚举到 x / primes[j] 时 x 会被筛去