Morning Star's blog
  2. cplus

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

算法一

根据质数的定义，当一个数只能被 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() 那一行。

TAGS