题目描述
给定一个正整数n,请你求出1~n中质数的个数
样例
输入
8
输出
4
线性筛法
- 每次筛去最小质因子和他的倍数
- 遍历到n 然后1的思想得
primes[j] <= n / i
- 更新bool数组
st[primes[j]*i] = true
,然后判断是否有重复筛选
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1000010;
int primes[N], cnt;
bool st[N]; //确定是否为素数
bool get_primes(int n){
for(int i = 2; i <= n; i ++){
//如果为质数 装入数组
if(!st[i]) primes[cnt ++] = i;
//primes[j]*i<=n 控制只筛 < n 的数
//思想用筛去最小质因子和最小质因子成倍的数
for(int j = 0; primes[j] <= n / i; j ++){
//最小质因子筛合数
st[primes[j] * i] = true;
//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子,那么只可能是此时的primes[j]<i的
//最小质因子,所以primes[j]*i的最小质因子就是primes[j];
//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
//prime[j],之后接着用st[primes[j+1]*i]=true去筛合数时,就不是用最小质因子去更新了,因为i有最小
//质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子,此时就应该
//退出循环,避免之后重复进行筛选
if(i % primes[j] == 0) break;
}
}
}
int main(){
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}