AcWing 868. 筛质数-线性筛-打通疑惑点
原题链接
简单
作者:
现代修士o_O
,
2021-05-15 17:13:08
,
所有人可见
,
阅读 213
#include <iostream>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++)
{
//primes[j] <= n / i是用来控制范围的
//移项之后式子为 prime[j] * i <= x,
//也就是st括号里的那个为了数组不越界。如果写乘法的话有可能爆int
// 为什么j < cnt 不必要?
//首先知道 primes[cnt - 1] = 当前最大质数,分两种情况
// 当 i 不是质数,肯定会在primes[cnt - 1]之前就被 break 掉
// 当 i 是质数,那么也会被primes[cnt - 1] = 被 break掉
// 相当于 保证了 j < cnt
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
//primes[j] 从小到大
//i % pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子
//i % pj != 0, pj定小于i的所有质因子,所以pj也为pj*i最小质因子
//因此,在满足i%prime[j]==0这个条件之前以及第一次满足改条件时,
// prime[j]必定是prime[j]*i的最小因子。
}
}
}
int main()
{
int n;
scanf("%d", &n);
get_primes(n);
cout << cnt << endl;
return 0;
}