前言
Eratosthenes 筛法利用的原理是 任意整数 x 的倍数 2x，3x，… 等都不是质数 。
但是即便如此也会有重复标记的现象，例如12既会被2又会被3标记，在标记2的倍数时，12=6∗2
，在标记3的倍数时，12=4∗3 ，根本原因是没有找到唯一产生12的方式。
线性筛法
假设 i 是合数 t 的最大因数，t显然可能不唯一（例如 30 和 45 最大因数都是 15）。但是仔细想一想，必然有
t = i * p(p为小于 i 的质数) 。
p为什么比 i 小？因为 i 是 t 的最大因数。
为什么 p 一定是质数？因为如果 p 是合数，那么 i 就一定不是 t 的最大因数，因为 p可以再拆成若干素数相乘，这些素数再与 i 相乘会使因数更大。
既然如此，我们只需要把所有小于 i 的质数 p 都挨个乘一次好了。可是，真相真的是这样的嘛？
其实不是的，一不小心就忘记了最初的条件。我们要满足 i 是 t 的最大因数。如果 p 大于 i 的最小质因数，那 i 还是 t 的最大因数嘛？显然不是，任何一个合数都能唯一分解为有限个质数的乘积，除去这其中最小的质因数，其他的都乘起来就是最大因数 i 。所以我们不能让 p 大于 i 的最小质因数。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) primes[cnt++] = i;
//假设primes[0]为n最小的质因子,i为最大的因数，
//易知若primes[i]中i>0,则会进入循环后产生多余的标记。
for(int j = 0; primes[j] <= n / i; j ++)
{
//标记;primes[j]一定是primes[j]*i的最小质因子
st[primes[j]*i] = true;
//表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
//这样能保证每个数遍历一遍,而没有重复
if(i % primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
补充一个
当 i % primes[j] == 0 时，primes[j] 一定是 i 的最小质因子，因此 primes[j] 一定是 primes[j] * i 的最小质因子。
当 i % primes[j] != 0 时，说明i的最小质因子比primes[j]还要大，因此 primes[j] 一定是 primes[j] * i 的最小质因子。
为什么要在 == 0 的时候break掉
当 i 是 prime[j] 的倍数时，有i = k * prime[j] ，如果继续运算 j+1，
i * prime[j+1] = prime[j] * k * prime[j+1] # 这里prime[j]是最小的质因子
当 i 循环到 = k * prime[j+1] 时会和 i * prime[j+1] 重复 # 所以要跳出循环。
j < cnt 不必要，因为 primes[cnt - 1] = 当前最大质数
如果 i 不是质数，肯定会在中间就 break 掉
如果 i 是质数，那么 primes[cnt - 1] = i，也保证了 j < cnt
为什么不需要写j<cnt
- primes数组中存有<=i的所有质数
- 当i是合数时, prime[j]为i的最小质因子时break, j不会越界
- 当i是质数时, prime数组的最后一个元素就是i, 当pj==i时, break,依然不越界
通透
不是很理解佬说的这句话：当 i % primes[j] != 0 时，说明i的最小质因子比primes[j]还要大，因此 primes[j] 一定是 primes[j] * i 的最小质因子。
意思是：当i % p[j] != 0时，说明此时的p[j]不是i的最小质因子，但是经过循环，后面会出现 i的最小质因子时p[j]对吗
假设primes[j-1] 是2，primes[j]是3，i是15；
那么 15%2！=0 表示 2是 2×15 的最小质因子；
15%3==0 表示 3是3×15的最小质因子；
这两句话中的j含义不同。
其他的看不懂 看你的看懂了 太牛逼了！！
看了y总的课还看了几个题解都没看懂 看了大佬的题解豁然开朗
primes[j] <= n / i为啥要这样写，不能写成j<cnt吗？
能用一下 $\LaTeX$ 和 MarkDown 吗？看着好难受。。。
原来
i的含义是最大因子，感觉是acwing最佳解答，甚至是全网最佳解答了。关于欧拉筛，可以看一下这个动画
【中国大学生计算机设计大赛《素数筛选—欧拉线性筛选法详解》】
https://www.bilibili.com/video/BV1LZ42147dW?vd_source=9818165f15c74ae910ca176397431a58
最让我豁然开朗的一篇
## 巨棒
佬，太牛了
有启发
good
连贯清晰orz
666
这么好的解释 第一无疑！！！！
这么好的答案竟然不是第一，给我上去
tql大佬，通俗易懂
newbee
if(i % primes[j] == 0) break;
这里为什么要break;
能举个栗子解释一下吗？
因为primes[j]要小于等于i的最小质因数，primes[j]是从小到大枚举的，当i%primes[j]==0时，primes[j]刚好是i的最小质因数，再往下枚举下一个primes[j+1]的话，primes[j+1]>primes[j]，也就是primes[j+1]>i的最小质因数，就不符合我们的要求了
tql
nice啊