求小于等于n的质数个数
程序员文章站
2022-03-01 17:46:44
...
埃氏筛法(Eratosthenes筛选法)
算法基本思想:要得到自然数n以内的全部素数,必须把不大于n1/2的所有素数的倍数剔除,剩下的就是素数。
给出要筛数值的范围n,找出n以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用2的下一个没被筛掉的数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。
bool a[1000003];//记录i是否被剔除
int main()
{
int n;
while(cin>>n)
{
memset(a, 0, (sizeof(bool))*1000003);
for(int i=2;i<=sqrt(n);i++)//可能的因数
{
if(a[i]==1) continue;
for(int j=2;j*i<=n;j++)
{
a[j*i]=1;
}
}
int ans=0;
for(int i=2;i<=n;i++)
{
if(a[i]!=1)
ans++;
}
cout<<ans<<endl;
}
}