素数判定

程序员文章站 2022-03-17 13:52:57

素数定义：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。素数问题变化莫测，但万变不离其宗。素数问题最核心的就是如何判断一个数是否是素数。对于判断一个数m是否是素数，最原始的方法就是按照素数的定义，试除2开始到m-1的整数，如果无一例外地都不能整除，则该数一定是素数。实现程序如下： ......

　　素数定义：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

　　素数问题变化莫测，但万变不离其宗。素数问题最核心的就是如何判断一个数是否是素数。对于判断一个数m是否是素数，最原始的方法就是按照素数的定义，试除2开始到m-1的整数，如果无一例外地都不能整除，则该数一定是素数。实现程序如下：

#include <iostream>
using namespace std;

　 //判断是否是素数

　 int main() {

　　cout << "please inpout a number.";

　　　　int m;
　　　　cin >> m;
　　　　for (int i = 2; i < m; ++i)

　　　　　if (m%i == 0) {
　　　　cout << m << " isn't a prime\n";
   　　　　　　　return 1;
  　　　　　 }
　　　　cout << m << " is a prime\n";
　　　    return 0;
　　}

改进：我们知道如果一个数有因子的话，那么在它的平方根数以内就应该有，否则就没有因子。例如66的平方根在8与9之间，因为66不是素数，，则它一定有比8还小的因子，我们知道66的因子是2、3、6等。

　　现在我们就可以将m试除2到√m的整数，如果无一例外地都不能整除，则该数一定是素数。实现程序如下：

#include <iostream>
using namespace std;

　 //判断是否是素数

　　int main() {

　　　　cout << "please inpout a number.";
　　　　int m;
cin >> m;
double sqrtm = sqrt(m*1.0);
for (int i = 2; i < sqrtm; ++i)
　　if (m%i == 0) {
　　　　cout << m << " isn't a prime\n";
   　　return 1;
   }
　　　 cout << m << " is a prime\n";
　　　 return 0;
   }

　　改进：现在举个例子，判断102是否是素数，本来要从2试除到10。但事实上，中间的4、6、8、10也都无须试，只需要试除2、3、5、7。直接来说，就是只需要试除2到√m之间的所有素数即可。而所有素数（除了2和3）都满足6*i-1或6*i+1（i=1、2、3...）。那么代码又可以改进，如下：

　　#include <iostream>
　　using namespace std;

　　int main() {
　　　cout << "please inpout a number.";
　　　int m;
　　　cin >> m;

　　　　//两个较小数另外处理
　　　　if (m == 2 || m == 3)
  　　　　　return 1;
　　 double sqrtm = sqrt(m*1.0);
　　　　for (int i = 5; i <= sqrtm; i += 6)
  　　　　　　if (m %i == 0 || m % (i + 2) == 0)
   　　　　　　　　cout << m << " isn't a prime\n";
　　　　cout << m << " is a prime\n";
　　　　return 0;
　　}

　　下面这种方法也是本人借鉴别人的，如有侵权请联系我删除。

　　改进：素数有2、3、5、7、11、13、17、19、23、29...，观察可知：素数一定在6的倍数的左右，但6的倍数的左右不一定是素数，如23是素数，但25不是素数。则我们可以先通过这个条件将可能是素数的数筛选出来，然后采用方法三，代码如下：

　　#include <iostream>
　　using namespace std;

　　int main() {
　　　cout << "please inpout a number.";
　　　    int m;
　　　　cin >> m;
　　　　//两个较小数另外处理
　　　　if (m == 2 || m == 3)
  　　　　　 return 1;
　　　　//不在6的倍数两侧的一定不是质数
　　　　if (m % 6 != 1 && m % 6 != 5) {
  　　　　　　cout << m << " isn't a prime\n";
  　　　　　　return 0;
　　　　}

　　　　double sqrtm = sqrt(m*1.0);
　　　　//在6的倍数两侧的也可能不是质数
　　　　for (int i = 5; i <= sqrtm; i += 6)
  　　　　　if (m %i == 0 || m % (i + 2) == 0)
   　　　　　cout << m << " isn't a prime\n";
　　　　　//排除所有，剩余的是质数
　　　　　cout << m << " is a prime\n";
　　　　　return 0;
　　}

现在对这四种方法的效率进行测试，测试代码如下：

　　#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之间素数的耗时：