题目描述
找出1到n中所有的质数。
这个题解主要是为了阐述为什么线性筛要有if (i % primes[j] == 0) break; 这句话。
详情见代码中的注释,字太难打了没有打到专门的解析位置QAQ
算法1
埃氏筛
时间复杂度 近似于O(n)
埃氏筛比较好理解,对应get_primes_1,视屏中讲得很清楚,这里不再赘述
算法2
线性筛(欧拉筛)O(n)
对应get_primes_2,下面的注释详细解释了为什么有break这句话,视屏中这里没有
详细的解释,想了解的话可以参考看看
C++ 代码
// 质数定理:1~n中有n / lnn个质数
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010;
int cnt;
int primes[N];
bool st[N];
// 埃氏筛法 基于质数定理 接近于O(n) 10^6时和线性筛法差不多
void get_primes_1(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
for (int j = i + 1; i <= n; j += i) st[j] = true; // 把i这个质数能凑出来的所有数都删掉
}
}
}
// 线性筛法 保证每个合数只会被它的最小质因子筛掉,即可以记录每个数的最小质因子
// 保证每个数由最小质因子筛掉,并且每个数只有一个最小质因子,所以每个数只会筛一遍
void get_primes_2(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]作为最小质因子的筛掉
if (i % primes[j] == 0) break; // 为了保证每个数只会被筛一次
}
}
}
// 解释一下为什么有 if(i % primes[j] == 0) break; 这句话
/*
首先,当第一次出现了i % primes[j] == 0的时候,证明primes[j]是i的最小质因子,而且i是一个合数
如果此时不跳出的话,那么就会发生这句话:st[primes[j + 1] * i] = true; 也就是我们用primes[j + 1]筛掉了下一个数
但是其实此时primes[j + 1] * i的最小质因子并不是primes[j + 1],所以违反了我们要用每个数的最小质因子来筛掉它的约定
观察可以得到:我们筛掉的数是primes[j + 1] * i,而i可以分解为primes[j] * d(由于i % primes[j] == 0),
得到:primes[j + 1] * i == primes[j + 1] * primes[j] * d,i是每一次加1的,所以会一点一点的变大,
而我们已知:primes[j + 1] < primes[j],所以说,我们可以等i变到primes[j + 1] * d的时候用primes[j]来筛掉这个数,
就保证了是用它的最小质因子来筛掉它的。
例子:当i == 4 我们到 4 % 2 == 0 时就break了,不会去筛掉12,因为12的最小质因子是2而不是3
但如果此时我们不break,那么我们就会用3 * 4去筛掉12,这和我们约定的不一样,根据上面的证明,
我们发现4 = 2 * 2,所以我们相当于是用3 * 2 * 2(primes[j + 1] == 3)去筛掉12的,那我们可以
等到i == 6的时候,用2去筛掉12,可以证明,由primes[j + 1] * d组成的i一定会出现在之后,使得
我们可以用primes[j]去筛掉这个数
*/
int main()
{
int n;
cin >> n;
get_primes_2(n);
cout << cnt << endl;
return 0;
}