判断素数的四种方法，从慢到快（c++）！！！_c++判断素数

判断素数的四种方法，从慢到快（c++）！！！

1.四种方法（已封装可直接使用）

方法一

/*
从2开始到num-1，逐一判断
*/
bool isPrime_1(int num){
   if(num==1||num==4) 
      return 0;
   if(num==2||num==3)
      return 1;    
   for(int i=2;i<num;i++){
      if(num%i==0)
      return 0;
   }
   return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二

/*
从2开始到sqrt(num)，逐一判断
*/
bool isPrime_2(int num){
   if(num==1||num==4) 
      return 0;
   if(num==2||num==3)
      return 1;  
   int temp=sqrt(num);   
   for(int i=2;i<=temp;i++){
      if(num%i==0)
      return 0;
   }   
   return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法三

/*
若一个数不能整除2，则可以推出这个数不能整除2n（用奇数不能整除偶数即可证明）；
所以判断素数时，判断其不能整除2，那么该数也不能整除2n，在后续判断时便不用判断
能否整除2n只需判断其是否能整除2n+1即可（循环步长可改为2）
*/
bool isPrime_3(int num){
   if(num==1||num==4) 
      return 0;
   if(num==2||num==3)
      return 1;
   if(num%2==0)
      return 0;
   int temp=sqrt(num);
   for(int i=3;i<=temp;i+=2)
      if(num%i==0)
      return 0;
   return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法四

/*
一个数能整除另一个数，那么必能整除另一个数的因数
一个数不能整除另一个数，那么必不能整除另一个数的倍数

从5开始，6n、6n+1、6n+2、6n+3、6n+4、6n+5中，6n、6n+2、6n+3、6n+4都可以整除2，则这些数不是素数；
只需判断剩下的6n+1、6n+5（即6m-1、6m+1，6m两侧的数）是不是素数即可；
6n+1、6n+5不能整除2，则这些数不能整除2i（即6i、6i+2、6i+3、6i+4），
所以只需进一步判断能否整除6i+1、6i+5（不包括1，从5开始；即5+6i、5+6i+2）即可（循环的步长变为6）
*/
bool isPrime_4(int num)
{
   if(num==1||num==4) 
      return 0;
   if(num==2||num==3)
      return 1;
   if(num %6!= 1&&num %6!=5)
      return 0 ;
   int tmp =sqrt(num);
   for(int i=5;i<=tmp;i+=6) {       
      if(num%i==0||num%(i+2)==0)  
         return 0 ;
   }    
   /*改成如下会有错误，初步判断是靠近sqrt(num)的数没有取到
   for(int i=6;i<=tmp;i+=6) {       
      if(num%(i-1)==0||num%(i+1)==0)  
         return 0 ;
   }    
   */  
    return 1 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.判断素数四种方法的时间的比较（以400000为例）

#include<ctime>
#include<cmath>
#include<iostream>
using namespace std;

int main()
{
   int num=400000;
   int sum1,sum2,sum3,sum4;
   sum1=sum2=sum3=sum4=0;
   clock_t start1,start2,start3,start4,end1,end2,end3,end4;
   
   start1=clock();
   for(int i=1;i<=num;i++){
      if(isPrime_1(i))
         sum1++;
   }
   end1=clock()-start1;

   start2=clock();
   for(int i=1;i<=num;i++){
      if(isPrime_2(i))
         sum2++;
   }
   end2=clock()-start2;

   start3=clock();
   for(int i=1;i<=num;i++){
      if(isPrime_3(i))
         sum3++;
   }
   end3=clock()-start3;

   start4=clock();
   for(int i=1;i<=num;i++){
      if(isPrime_4(i))
         sum4++;
   }
   end4=clock()-start4;

   cout<<sum1<<' '<<sum2<<' '<<sum3<<' '<<sum4<<endl;
   cout<<end1<<"ms "<<end2<<"ms "<<end3<<"ms "<<end4<<"ms "<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

输出结果，从左到右分别为方法一二三四；第一行为1-400000的素数个数，第二行为各方法运行时间