给定一个正整数 nn,请你求出 1∼n1∼n 中质数的个数。
输入格式
共一行,包含整数 nn。
输出格式
共一行,包含一个整数,表示 1∼n1∼n 中质数的个数。
数据范围
1≤n≤1061≤n≤106
输入样例:
8
输出样例:
4
#include <iostream>
using namespace std;
const int N=1e6+10;
int cnt;
bool st[N];
int primes[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;// for(int i=0;i<cnt;i++)// {// cout<<primes[i]<<endl;// }
}
#include <iostream>
using namespace std;
const int N=1e6+10;
int cnt;
bool st[N];
int primes[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;if(i%primes[j]==0) break;}}
}
int main()
{int n;cin>>n;get_primes(n);cout<<cnt<<endl;// for(int i=0;i<cnt;i++)// {// cout<<primes[i]<<endl;// }
}