C++常见的质数判断算法

        质数定义：一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除。

        算法1：（定义）判断一个整数n是否为质数，只需用2到n-1之间的每一个整数去除，如果都不能被整除，那么n就是一个质数

#include <iostream>
#define MAX 100

using namespace std;

int main() {
	int j;
	for (int i = 2; i <= MAX; i++) {
		for (j = 2; j < i; j++) {
			if (i % j == 0)
				break;
		}
		if (j == i)
			cout << i << endl;
	}
	return 0;
}

        算法2：（质数筛选定理）n不能够被不大于根号n的任何质数整除，则n是一个质数

#include <iostream>
#include <cmath>
#define MAX 100

using namespace std;

int main() {
	for (int i = 2; i <= MAX; i++) {
		float temp = static_cast<float>(i);
		int mid = static_cast<int>(sqrt(temp)); //sqrt函数参数和返回值均没有int型。
		int j;
		for (j = 2; j <= mid; j++) {
			if (i % j == 0)
				break;
		}
		if (j > mid)
			cout << i << endl;
	}
	return 0;
}

上面的算法还能改进，因为偶数都不是质数，运算量会下降一半。

        算法2改进：

#include <iostream>
#include <cmath>    // for sqrt()
#define MAX 100

using namespace std;

int main() {
	cout << 2 << endl; //2是质数
	for (int i = 3; i <= MAX; i += 2) { //偶数不是质数，步长可以加大
		float temp = static_cast<float>(i);
		int mid = static_cast<int>(sqrt(temp));
		int j;
		for (j = 3; j <= mid; j += 2)//i是奇数，当然不能被偶数整除，步长也可以加大。
			if (i % j == 0)
				break;

		if (j > mid)
			cout << i << endl;
	}
	return 0;
}

        算法3：Miller-Rabin算法

        Miller-Rabin算法是目前主流的基于概率的素数测试方法。素数测试算法主要分两种：概率素数测试算法和真素数测试算法。 概率素数测试算法的特点是：算法速度较快、原理简单、易于编程实现、有一定的误判概率。与之相比，真素数 测试算法最大的特点是不存在误判，但从应用角度讲，真素 数测试算法不如概率测试算法实用。最大的原因是：真素数 测试算法相对较慢。

        Miller-Rabin算法理论艰深，但是实际应用还是比较多，后续再学习。