素数的几种判断方法总结（含C++代码）

2023-05-16

素数的几种判断方法总结（含C++代码）

一、素数定义
二、素数判断方法
- - 1.定义法
  - 2.定义法改进
  - 3.取模法
  - 5.筛选法改进
三、总结

一、素数定义

素数（prime number），也称质数，是指大于1的自然数中因数只有1和它本身的数。例如，2是素数，其只有1和2两个因数；29是素数，其只有1和29两个因数；51不是素数，除了1和51，它还有3和17两个因数，故称51为合数。

二、素数判断方法

给定一个正整数n (n≥2)：

1.定义法

即将n除以[2,n-1]的所有整数，若有其中一个数运算后的余数为0，也就是说这个数是n的因数，故n不为素数。代码如下：

bool isPrime(int n){
 bool yes=true;
 for(int i=2;i<n;i++){
  if(n%i==0){
   yes=false;
   break;
  }
 }
 return yes;
}

2.定义法改进

由于n的因数总是成对出现的，且分别分布在[1, n \sqrt n n ]和[ n \sqrt n n ,n]范围内（若因数为 n \sqrt n n ，我们当作两个重复的因数），那么我们只需判断一个范围即可。代码如下：

bool isPrime2(int n){
 bool yes=true;
 for(int i=2;i<=sqrt(n);i++){
  if(n%i==0){
   yes=false;
   break;
  }
 }
 return yes;
}

3.取模法

当n≥6时，由于n可以表示为6x+1、6x+2、6x+3、6x+4、6x+5、6x (x≥1)中的一种，那么，若n的表达式为6x+2、6x+4或6x，很显然n不是素数；故，当n的表达式为6x+1或6x+5时，可能为素数，再应用方法2。代码如下：

bool isPrime3(int n){
 bool yes=false;
 if(n==2||n==3||n==5){ //当n<6时列举即可
  yes=true;
 }
 else if(n%6==1||n%6==5){ //通过判断余数的方式来判断n的表达式
  yes=true;
  for(int i=2;i<=sqrt(n);i++){
   if(n%i==0){
    yes=false;
    break;
   }
  }
 }
 return yes;
}

测试一下，消耗时间为

### 4.筛选法（Eratosthenes筛选）
我们可以很容易的判断出2、3、5等较简单的数是素数，而且，当一个数是素数后，它的倍数一定为合数。因此，我们可以将一定范围的整数筛选掉合数，剩下的即是素数。代码如下：

```cpp
bool isPrime4(int n){
 bool yes=false;
 //先生成一定范围的整数表，再应用筛选法，得到素数表，最后与素数表比对
 //生成0~100000内的素数表
 int num[100000]={0}; //0表示素数，1表示合数
 for(int i=2;i<100000;i++){
  if(!num[i]){
   for(int j=i+i;j<100000;j+=i){
    num[j]=1;
   }
  }
 }
 if(!num[n]){
  yes=true;
 }
 return yes;
}

5.筛选法改进

首先，我们可以肯定，除了2以外的所有素数是奇数，因此可以建立一个表示大于2的奇数数组，这样既扩大了判断范围，又减少了判断次数；然后，我们得到这个奇数数组3、5、7、9……以3为例，按方法4我们应该筛掉3×2、3×3、3×4……但是其中3×2、3×4……是偶数，已经被筛掉了，因此只需从3×3开始，筛掉3×3、3×5、3×7……而当筛选5的倍数时，同样应该以5×2开始，但是5×2、5×4……为偶数，那么就应该考虑从5×3开始，但5×3已经在筛选3的倍数时筛掉了，所以筛选5的倍数时应该从5×5开始，筛掉5×7、5×9……当我们多观察几组数的筛选后，会有这样的规律：若a为素数，那么从a×a开始筛选，筛掉a×a+2×a×i（i=0，1，2……）。
从a×a开始筛的原因：按方法4我们应该筛掉a×2、a×3、a×4……其中a×2、a×4……为偶数，已经筛掉了，当从a×3开始筛选时，若a>3，可以肯定，在筛选3的倍数时已经筛掉3×a这个数了，那么从a×5开始筛选，同理，若a>5，则在筛选5的倍数时已经筛掉5×a这个数了；这样一直到从a×a开始筛选，才没有被之前的过程筛掉。
为什么筛掉a×a+2×a×i（i=0，1，2……）？我们可以将这个式子转化一下：a×a+2×a×i=a×(a+2×i)。可以看出当从a×a开始筛选时，筛掉a×(a+0)、a×(a+2)、a×(a+4)……符合前面过程中的规律。
将上述过程总结成代码：

bool isPrime5(int n){
 bool yes=false;
 int num[100000]={0}; //生成3~2*99999+3范围内的奇数数组
 //先判断当n=2时的情况
 if(n==2){
  yes=true;
 }
 else{
  for(int i=0;i<100000;i++){
   if(!num[i]){
    for(int j=(2*i+3)*(2*i+3);j<(2*100000+3);j+=2*(2*i+3)){
     num[(j-3)/2]=1;
    }
   }
  }
 }
 if((n-3)%2==0){
  if(!num[(n-3)/2]){
   yes=true;
  }
 }
 return yes;
}

三、总结

将上述几种方法放到一起，代码如下：

#include <iostream>
#include <math.h>
#include <time.h>
#define SIZE 10000
using namespace std;
bool isPrime(int n) {
 bool yes = true;
 for (int i = 2; i < n; i++) {
  if (n % i == 0) {
   yes = false;
   break;
  }
 }
 return yes;
}
bool isPrime2(int n) {
 bool yes = true;
 for (int i = 2; i <= sqrt(n); i++) {
  if (n % i == 0) {
   yes = false;
   break;
  }
 }
 return yes;
}
bool isPrime3(int n) {
 bool yes = false;
 if (n == 2 || n == 3 || n == 5) {
  yes = true;
 }
 else if(n%6==1||n%6==5) {
  yes = true;
  for (int i = 2; i <= sqrt(n); i++) {
   if (n % i == 0) {
    yes = false;
    break;
   }
  }
 }
 return yes;
}
bool isPrime4(int n) {
 bool yes = false;
 int num[SIZE] = { 0 };
 for (int i = 2; i < SIZE; i++) {
  if (!num[i]) {
   for (int j = i + i; j < SIZE; j += i) {
    num[j] = 1;
   }
  }
 }
 if (!num[n]) {
  yes = true;
 }
 return yes;
}
bool isPrime5(int n) {
 bool yes = false;
 int num[SIZE] = { 0 };
 if (n == 2) {
  yes = true;
 }
 else {
  for (int i = 0; i < SIZE; i++) {
   if (!num[i]) {
    for (int j = (2 * i + 3) * (2 * i + 3); j < (2 * SIZE + 3); j += 2 * (2 * i + 3)) {
     num[(j - 3) / 2] = 1;
    }
   }
  }
 }
 if ((n - 3) % 2 == 0) {
  if (!num[(n - 3) / 2]) {
   yes = true;
  }
 }
 return yes;
}
int main() {
 cout << "function isPrime():" << endl;
 time_t before = clock();
 for (int i = 2, j = 0; i < 10000; i++) {
  if (isPrime(i)) {
   cout << i << " ";
   j++;
  }
  if (j == 9) {
   cout << endl;
   j = 0;
  }
 }
 time_t after = clock();
 cout << endl;
 cout << static_cast<double>((after - before) * 1000 / CLOCKS_PER_SEC) << "(ms)" << endl;
 cout << "function isPrime2():" << endl;
 before = clock();
 for (int i = 2, j = 0; i < 10000; i++) {
  if (isPrime2(i)) {
   cout << i << " ";
   j++;
  }
  if (j == 9) {
   cout << endl;
   j = 0;
  }
 }
 after = clock();
 cout << endl;
 cout << static_cast<double>((after - before) * 1000 / CLOCKS_PER_SEC) << "(ms)" << endl;
 cout << "function isPrime3():" << endl;
 before = clock();
 for (int i = 2, j = 0; i < 10000; i++) {
  if (isPrime3(i)) {
   cout << i << " ";
   j++;
  }
  if (j == 9) {
   cout << endl;
   j = 0;
  }
 }
 after = clock();
 cout << endl;
 cout << static_cast<double>((after - before) * 1000 / CLOCKS_PER_SEC) << "(ms)" << endl;
 cout << "function isPrime4():" << endl;
 before = clock();
 for (int i = 2, j = 0; i < 10000; i++) {
  if (isPrime4(i)) {
   cout << i << " ";
   j++;
  }
  if (j == 9) {
   cout << endl;
   j = 0;
  }
 }
 after = clock();
 cout << endl;
 cout << static_cast<double>((after - before) * 1000 / CLOCKS_PER_SEC) << "(ms)" << endl;
 cout << "function isPrime5():" << endl;
 before = clock();
 for (int i = 2, j = 0; i < 10000; i++) {
  if (isPrime5(i)) {
   cout << i << " ";
   j++;
  }
  if (j == 9) {
   cout << endl;
   j = 0;
  }
 }
 after = clock();
 cout << endl;
 cout << static_cast<double>((after - before) * 1000 / CLOCKS_PER_SEC) << "(ms)" << endl;
 return 0;
}

我们运行上述代码（运行环境：vs2019，debug，x64），消耗时间结果如下：
isPrime()：379ms
isPrime2()：370ms
isPrime3()：400ms
isPrime4()：1008ms
isPrime5()：1028ms
发现方法2的效率最高。可能是我的代码有待优化，方法3的效率并不高。而方法4和方法5由于需要先生成一个素数表，再进行比对，消耗的时间一定会增加。如果是生成一个素数表，而不是判断一个整数是否为素数，这两种方法效率或许比较高。其中方法5生成的素数表范围更大。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)