- 法一：
- √n判别
- 这个的话就是暴力了吧，不过只能判别单个数是不是质数，而且很大的话会爆
-
//没有代码qwq（不想写
- 法二：埃式筛法
- O(nloglogn)判别
- 直接代码好不啦：
-
int pri[100000],n,num; bool yes[100010]; sieve(int a)//筛 { for(int i=1;i<=a;i++)yes[i]=1; for(int i=2;i<=a;i++){ if(yes[i]){ pri[++num]=i; for(int j=i*2;j<=a;j+=i) yes[j]=0;} } } int main() { cin>>n; sieve(n); for(int i=1;i<=num;i++) cout<<pri[i]<<endl; }//伪代码qwq - 法三：线形筛：
-
int pri[10000],n,num; bool yes[10010]; int hs(int a){ num=0; memset(yes,0,sizeof(yes)); for(int i=2;i<=a;i++){ if(!yes[i])pri[num++]=i; for(int j=0;j<=num&&i*pri[j]<=a;j++){ yes[i*pri[j]]=1; if(i%pri[j]==0)break; } } } int main() { cin>>n; hs(n); for(int i=1;i<num;i++) cout<<pri[i]<<endl; }end-