题目描述
给定一个正整数n,请你求出1~n中质数的个数。
输入格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示1~n中质数的个数。
数据范围
1≤n≤106
样例
输入样例:
8
输出样例:
4
埃氏筛法
线性筛法
埃氏筛法
时间复杂度:O(nloglogn)几乎为O(n)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10000010;
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=i+i;j<=n;j+=i){
st[j]=true;
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}
线性筛法
时间复杂度:(在对1e7及以上个数筛时比埃氏筛法快一倍,1e6及以下两种都差不多)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10000010;
int primes[N],cnt;
bool st[N];
//线性筛法:
//时间复杂度:O(nloglogn)几乎为O(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++){
st[primes[j]*i]=true;//将最小质因子为primes[j]的合数标记为true
if(i%primes[j]==0)break;//primes[j]一定是i的最小质因子
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}