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

　　

　　int isPrime_1(int num);
　　int isPrime_2(int num);
　　int isPrime_3(int num);
　　int isPrime_4(int num);

　　int main(){
 　   　　int num = 30000;
 　　　   int tstart, tstop; //分别记录起始和结束时间

 

　　　　//测试第一个判断质数函数
 　　　　tstart = clock();
 　　　　for (int i = 1; i <= num; i++)
 　　　　　　 isPrime_1(i);
 　　　　tstop = clock();
 　　　　cout << "isPrime_1方法的时间(ms):" << tstop - tstart << endl;

 　　　　

　　　　//测试第二个判断质数函数
 　　　　tstart = clock();
　　　　 for (int i = 1; i <= num; i++)
 　　　　　　 isPrime_2(i);
 　　　　tstop = clock();
 　　　　cout << "isPrime_2方法的时间(ms):" << tstop - tstart << endl;

 

　　　　//测试第三个判断质数函数
 　　　　tstart = clock();
 　　　　for (int i = 1; i <= num; i++)
  　　　　　　isPrime_3(i);
 　　　　tstop = clock();
 　　　　cout << "isPrime_3方法的时间(ms):" << tstop - tstart << endl;

 　　　　

　　　　//测试第四个判断质数函数
 　　　　tstart = clock();
　　　　 for (int i = 1; i <= num; i++)
  　　　　　　isPrime_4(i);
　　　　 tstop = clock();
 　　　　cout << "isPrime_4方法的时间(ms):" << tstop - tstart << endl;

 　　　　cout << endl;
 　　　　return 0;
　　}

 

　　int isPrime_1(int num){
 　　　　for (int i = 2; i <= num - 1; i++)
  　　　　　　if (num %i == 0)
   　　　　　　　　return 0;
 　　　　return 1;
　　}

 

　　int isPrime_2(int num){
 　　　　double sqrtnum = sqrt(num*1.0);
 　　　　for (int i = 2; i <= sqrtnum; i++)
  　　　　　　if (num %i == 0)
   　　　　　　　　return 0;
 　　　　return 1;
　　}

 

　　int isPrime_3(int num) {
 　　　　//两个较小数另外处理
 　　　　if (num == 2 || num == 3)
  　　　　　　return 1;

 　　　　double sqrtnum = sqrt(num*1.0);
 　　　　for (int i = 5; i <= sqrtnum; i += 6)
  　　　　　　if (num %i == 0 || num % (i + 2) == 0)
   　　　　　　　　return 0;
 　　　　return 1;
　　}

 

　　int isPrime_4(int num){
 　　　　//两个较小数另外处理
 　　　　if (num == 2 || num == 3)
  　　　　　　return 1;
 　　　　//不在6的倍数两侧的一定不是质数
 　　　　if (num % 6 != 1 && num % 6 != 5)
  　　　　　　return 0;
 　　　　double sqrtnum = sqrt(num*1.0);
 　　　　//在6的倍数两侧的也可能不是质数
 　　　　for (int i = 5; i <= sqrtnum; i += 6)
  　　　　　　if (num %i == 0 || num % (i + 2) == 0)
   　　　　　　　　return 0;
 　　　　//排除所有，剩余的是质数
 　　　　return 1;

　　}

判断1-30000之间素数的耗时：

现在测试判断1-300000之间素数的耗时：

方法二和方法三的效率之间相差其实不大，什么原因大家可以思考思考。

判断素数的方法就讨论到这，有什么想法大家可以指出。