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

一、素数定义

素数（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;
}
1
2
3
4
5
6
7
8
9
10

2.定义法改进

由于n的因数总是成对出现的，且分别分布在[1,$\sqrt{n}$]和[$\sqrt{n}$,n]范围内（若因数为$\sqrt{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;
}
1
2
3
4
5
6
7
8
9
10

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试一下，消耗时间为

### 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、总结

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

#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;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

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