AcWing 868. 筛质数
原题链接
简单
作者:
chaosliang
,
2021-01-22 20:53:42
,
所有人可见
,
阅读 249
线性筛法
理解性记忆
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6+5;
int primes[N], cnt;
bool st[N];
//算术基本定理可以推出:每一个合数t可以表示为一个最小质因数x与另一个数y的乘积,
//这里x唯一,于是,每一个合数t都可以用唯一的一个数(最小质因子x)筛掉
void get_primes(int n)
{
for(int i = 2; i <= n; ++ i) //遍历y
{
if(!st[i]) primes[cnt ++] = i; //是质数
for(int j = 0; primes[j] <= n/i; ++ j) //遍历x
{
st[primes[j]*i] = true;
//说明y中也存在一个x,那么下一个新的质数肯定不是最小质因子(比x大)
if(i%primes[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}