欧拉筛法

原理解释

一个合数只能被以下方法去掉
“最小质因数 × 最大因数（非自己） = 这个合数”
这个方法保证一个合数只被去掉一次
没有重复去除保证了时间复杂度为O(n)。

原理概述

代码中，外层枚举 i=1→n。对于一个 i ，经过前面的腥风血雨，如果它还没有被筛掉，就加到质数数组 Prime[]中。下一步，是用 i 来筛掉一波数。内层从小到大枚举 Prime[j]。 i×Prime[j] 是尝试筛掉的某个合数，其中，我们期望 Prime[j] 是这个合数的最小质因数 (这是线性复杂度的条件，下面叫做“筛条件”)。
它是怎么得到保证的？
j 的循环中，有一句就做到了这一点：

if (i % primes[j] == 0) break;

j 循环到 i mod Prime[j]==0 就恰好需要停止的理由是：

• 下面用 s(smaller) 表示小于 j 的数， L(larger) 表示大于 j 的数。
• 1. i 的最小质因数肯定是 Prime[j] 。(如果 i 的最小质因数是 Prime[s] ，那么 Prime[s] 更早被枚举到(因为我们从小到大枚举质数)，当时就要break)。
• 2. i×Prime[s] 的最小质因数确实是 Prime[s] 。(如果是它的最小质因数是更小的质数 Prime[t] ，那么当然 Prime[t] 更早被枚举到，当时就要break)这说明 j 之前（用 i×Prime[s] 的方式去筛合数，使用的是最小质因数）都符合“筛条件”。
• 3. i×Prime[L] 的最小质因数一定是 Prime[j] 。(因为 i 的最小质因数是 Prime[j] ，所以 i×Prime[L] 也含有 Prime[j] 这个因数（这是 i 的功劳），所以其最小质因数也是 Prime[j] （新的质因数 Prime[L] 太大了这说明，如果 j 继续递增（将以 i×Prime[L]的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

Tips

当 i 还不大的时候，可能会一层内就筛去大量合数，看上去耗时比较大，但是由于保证了筛去的合数日后将不会再被筛（总共只筛一次），复杂度是线性的。到 i 接近 n 时，每层几乎都不用做什么事。

原理图

原理图来自CSDN博客

代码

const int N = 10000010;
int st[N], prime[N], n, cnt;
void get_primes(int n)  //线性筛素数
{
  for (int i = 2; i <= n; i++) {
    if (!st[i]) prime[++cnt] = i;  //将素数存入素数数组
    for (int j = 1; prime[j] * i <= n; j++) {
      st[prime[j] * i] = 1;          //素数的倍数标记为非素数
      if (i % prime[j] == 0) break;  //如果这个数是循环到素数的倍数结束循环
    }
  }
}

Q.E.D.