AcWing 868. 筛质数
原题链接
简单
作者:
ARi_King
,
2019-10-28 20:18:00
,
所有人可见
,
阅读 654
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int found[N], P[N], cnt;
int main()
{
//先预先说一下这个筛法的大致过程
//发现2是质数 now:i == 2 筛掉4
//发现3是质数 i == 3 筛掉6 9
// i == 4 筛掉8 12(这里忘记break了 所以导致12与下面重复筛了一次)
//发现5是质数 i == 5 筛掉10 15 25
// i == 6 筛掉12 break;
//发现7是质数 i == 7 筛掉14 21 35
// i == 8 筛掉16 break;
// i == 9 筛掉18 27 break;
int n; cin >> n;
for(int i = 2; i <= n; i++)
{
if(!found[i]) P[cnt++] = i;
for(int j = 0; P[j] <= n / i; j++)
{
found[P[j] * i] = 1; //對這一步而言i的作用就是 將每個質數的i倍篩掉
if(i % P[j] == 0) break; //如果當前的質數是i的因子 則需要break 不然下一輪的P[j] * i所篩掉的一定會在某個時刻重複
//如 15 % 3 == 0; 15 * 5 == 3 * 25;
//P[j] 不是 P[j] * i的最小質因子只有下列幾種情況
//1.i比P[j]小 2.i比P[j]大 但i是合數 且i的最小質因子大於P[j]
//第一種情況沒有可能
//第二種情況的原因是如果i = x * p && p < P[j] 則i * P[j] == p * (x * P[j])
//後者必將在將來重複一次
}
}
cout << cnt;
}
这模拟 ,爱了
thx!