基本思想 :2 3 4 5 6 7 8 9 10 11 12
从头开始枚举,列表中是当前枚举数的倍数就删掉(算法题里我们删掉通常是打上标记)
简单说明: 如果能枚举到当前的P,那就说明在2-p-1中没有p的因子,在p之后更不会有他的因子,那么这个P符合质数的定义(只有本身P和1是他的因子)
C++
#include<iostream>
#include<algorithm>
using namespace std;
int const maxn=1000010;
int primes[maxn],ans;
bool st[maxn];
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(st[i]) continue;
primes[ans++]=i; ///prime[0]=2;prime[1]=3;prime[2]=5;(以基本思想中的例子为例)
for(int j=i+i;j<=n;j+=i)
st[j]=true;
}
}
int main(void)
{
int n;
cin>>n;
get_primes(n);
cout<<ans<<endl;
return 0;
}
路过,发现一个眼熟的带佬(
菜鸡被大佬 评论了好开心~~~