判断质数(素数)算法的C++实现

求质数,或是判断一个数是否是质数有多种算法,每种算法的时间、空间的占用各部相同。本文演示几种常用的算法。

算法一

根据质数的定义,当一个数只能被 1 和自身整除的时候,该数为质数。 更加这个定义,我们可以写出一个很直观的代码:

1
2
3
4
5
6
7
8
9
10
bool isPrime0(int num) {

int i;
for (i = 2; i < num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}

算法二

算法一的主要问题是太慢,改进的方法是减少每次循环的次数。 代码:

1
2
3
4
5
6
7
8
9
10
bool isPrime1(int num) {
int i;
for (i = 2; i < sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}

return true;
}

算法三

在算法二的基础上,用简单的方法快捷的剔除一些情况,比如,偶数一定不是质数。 改进代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime2(int num) {
int i;
if (num % 2 == 0) {
return false;
}
for (i = 3; i < sqrt(num); i = i + 2) {
if (num % i == 0) {
return false;
}
}

return true;
}

算法四

如果需要判断大量的数,比如: 找出 1 ~ 10000000 内的所有质数这样的题,用上面的三种算法就比较慢,这个时候就需要考虑用空间换时间的方法,采用筛选法,实例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAX_COUNT 100000000+1

void makePrime() {
memset(a, 1, sizeof(a));
a[0] = 0;
a[1] = 0;
long end = sqrt(MAX_COUNT);
for (int i = 2; i < end; i++) {
if (a[i]) {
for (long k = i * i; k < MAX_COUNT; k += i) {
a[k] = 0;
}
}
}
}

bool isPrime3(int n) {
return a[n];
}

在该算法中,需要先首先调用 makePrime 构建整个筛选表。然后每次在调用 isPrime3 对每个数进行判断。

经测试,算法四的效率(包括 makePrime 和每次 isPrime3 调用)是前三种算法效率的百倍以上。

测试代码如下:

1
2
3
4
5
6
7
makePrime();

for (int i = 2; i < MAX_COUNT; i++) {
if (isPrime3(i)) {
res += i;
}
}

在测试其它算法是需要注释掉 makePrime() 那一行。

本文标题:判断质数(素数)算法的C++实现

文章作者:Morning Star

发布时间:2021年01月19日 - 15:01

最后更新:2021年04月16日 - 15:04

原始链接:https://www.mls-tech.info/cplus/cplus_detect_prime/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。