不陌生的素数

1.判断一个数是否为素数的普通方法

复杂度 O(√n)

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 
 7 bool prime(int x);
 8 
 9 int main(){
10     //freopen("E:\input.in","r",stdin);
11     //freopen("E:\output.out","w",stdout);
12     int x;
13     scanf("%d",&x);
14     if(prime(x))   printf("true
");
15     else    printf("false
");
16     return 0;
17 }
18 bool prime(int x){
19     if(x<2){
20         return false;
21     }
22     int x2=(int)sqrt((double)x);
23     for(int i=2;i<=x2;i++){
24         if(!(x%i)){
25             return false;
26         }
27     }
28     return true;
29 }

2.标准的爱拉托逊斯筛选法-筛选出一个范围内的所有素数

实际复杂度 O(nlognlogn)

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int N=1e5;
 8 bool b[N];
 9 
10 void isPrime(int n);
11 
12 int main(){
13     //freopen("E:\input.in","r",stdin);
14     //freopen("E:\output.out","w",stdout);
15     int n;
16     scanf("%d",&n);
17     isPrime(n);
18     int x;
19     scanf("%d",&x);
20     if(b[x])    puts("true");
21     else    puts("false");
22     return 0;
23 }
24 void isPrime(int n){
25     memset(b,1,sizeof(b));
26     int m=n>>1;
27     for(int i=2;i<=m;i++){
28         if(!b[i])   continue;
29         for(int j=i+i;j<=n;j+=i){
30             b[j]=0;
31         }
32     }
33 }

3.改进的爱拉托逊斯筛选法

复杂度 O(nlognlogn)

 1 #include <fstream>
 2 #include <iostream>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int N=1e5;
 8 bool b[N];
 9 int p[N],np;
10 
11 void isPrime(int n);
12 
13 int main(){
14     //freopen("E:\input.in","r",stdin);
15     //freopen("E:\output.out","w",stdout);
16     int n;
17     scanf("%d",&n);
18     isPrime(n);
19     int x;
20     scanf("%d",&x);
21     if(b[x])    puts("true");
22     else    puts("false");
23     return 0;
24 }
25 void isPrime(int n){
26     memset(b,1,sizeof(b));
27     for(int i=2;i<=n;i++){
28         if(b[i])   p[np++]=i;
29         for(int j=0;j<np&&p[j]*i<=n;j++){
30             b[p[j]*i]=0;
31             if(i%p[j]==0) break;//使得任何一个合数，只被它最小的质因数标记过一次
32         }
33     }
34 }