线性筛
n 只会被它的最小质因子 筛掉
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,k,pri[N];
bool st[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 2;i <= n; ++i){
if(!st[i]) pri[k++] = i;
for(int j = 0;pri[j] <= n / i; ++j){
st[pri[j] * i] = 1;
if(i % pri[j] == 0) break; // pri[j] 一定是 i 的最小质因子
}
}
cout << k << endl;
return 0;
}
分情况讨论 :
- i % pri[j] == 0
pri[j] 一定是 i 的最小质因子,因为是从小到 大枚举的 pri[j]
所以 pri[j] 一定是 pri[j] * i 的最小质因子 (pri[j] 已经是质数了,它除了1和自身没有其他的约数).
- i % pri[j] != 0
从小到 大 枚举 i 的质因子,并且没有枚举到 i 的任何一个质因子
所以 ,当前 的 pri[j] 一定小于 i 的所有质因子 ,
所以 , pri[j] 也一定是 pri[j] * i 的最小质因子
并且 ,合数一定会被筛掉
对于任何 一个 合数 x ,假设 pj 是 x 的最小质因子,当 i 枚举到 x / pj 的时候
st[ pri[j] * i] == st[ x ] 一定会被筛掉