素数 高速判定并打表
素数 快速判定并打表
#include<iostream>
#include<cmath>
using namespace std;
const int N=10001;
int prime[N],t=0;
bool Is_or[N];
void Prime_is()
{
for(int i=1;i<=N;i++)
Is_or[i]=1;
for(int j=2;j<=sqrt(N);j++)
{
if(Is_or[j])
for(int k=j+j;k<=N;k+=j)
Is_or[k]=0;
}
for(int q=1;q<=N;q++)
{
if(Is_or[q])
{
prime[t++]=q;
}
}
}
int main()
{
int p;
Prime_is();
for(p=1;p<t;p++)
cout<<prime[p]<<" ";
return 0;
}