线性筛法
参考文献
https://www.acwing.com/activity/content/code/content/5374176/
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int primes[N], cnt;
bool st[N];
//线性筛,根据每个合数的最小质因数把合数筛掉,如可以由2把4和8筛掉
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[i]为最小质因数的合数
if(i%primes[j]==0) break;//如果刚好能被整除择进行下一个循环,寻找下一个质数
}
}
}
int main()
{
int n;
cin>>n;
get_primes(n);
cout<<cnt<<endl;
return 0;
}