求n以内的素数-从入门到入坟思维导图

最简单的方法，对n以内所有数进行试除

要点

bool prime(int x){ if(x<=1) return 0; for(int i=2;i*i<=n;i++){ if(x%i==0) return 0; } return 1; }

缺点

原理

for(int i=2;i<=n;i++){ for(int j=2;i*j<=n;j++){ book[i*j]=1; } }

时间复杂度略有降低，约n*log2(n)

缺点

在朴素筛的基础上加入一条判断条件以及第二重循环小优化

for(int i=2;i<=n;i++){ if(book[i]==0){ for(int j=i;i*j<=n;j++){ book[i*j]=1; } } }

时间复杂度大大降低，约为O(NlnlnN)，已经接近于O(N)级别

缺点

由于埃氏筛任由重复运算，其实并不是最快

欧拉筛将素数存储在数组中，第二重循环将i的prime[j]倍的数筛除，同时当i是prime[j]的倍数是退出循环。保证每个合数只计算一次

for(int i=2;i<=n-1;i++){ if(book[i]==0){ cnt++; prime[cnt]=i; } for(int j=1;prime[j]*i<n;j++){ book[i*prime[j]]=1; if(i%prime[j]==0) break; } }

因其对每一个合数只会筛除一次，时间复杂度为O(n)，目前最快的筛法