质数判定的常数优化

注意：下面可能有部分数学符号使用不规范，看懂就行。

如何迅速判断 /(n/) 是否为质数？

方法一

枚举 /(i/) 满足 /(1 < i < n/)，则 /(n/) 不是质数，当且仅当全部的 /(i /nmid n/)。

时间复杂度 /(O(n)/)。

bool isp(int n) //isp = is_prime
{
	if (n <= 1) return false;
	for (int i = 2; i < n; i++)
		if (n % i == 0)
			return false;
	return true;
}

太慢了，考场绝对不要用。

方法二

若 /(i/mid n/)，则 /(n /div i /mid n/)。

所以，/(i/) 实际只需枚举到 /(/sqrt{n}/)。

时间复杂度显然为 /(O(/sqrt{n})/)。

bool isp(int n) //isp = is_prime
{
   if (n <= 1) return false;
   for (int i = 2; i*i <= n; i++)
   //计算机处理乘法（或乘方）要比除法（或根式）要快。
   //所以，i <= sqrt(n) 写成 i*i <= n 可以微小优化。
   	if (n % i == 0)
   		return false;
   return true;
}

效率还不错，大部分人都打这个。

但是，还有更快的方法，你可曾听过？

方法三

方法二还不是最快的，主要原因是仍然有很多计算可以舍去。

例如说，如果 /(2 /nmid n/)，显然 /(4 /nmid n/)，这就是重复计算。

怎么避免重复计算呢？答案是尽可能地用质数检验。

我们考虑 /(/bmod 6/)，对于 /(n /le 5/) 的情况可以直接特判掉。

看 /(n /ge 6/) 的情况。此时 /(n /bmod 6 = 0, 1, 2, 3, 4, 5/)。

容易想到，/(n /bmod 6 = 0, 2, 3, 4/) 必定不是质数，它们分别会被 /(6, 2, 3, 2/) 整除。

所以说，若 /(n/) 为质数，至少满足 /(n /bmod 6 = 1, 5/)。

所以，我们可以直接检验这些数，因为这样 /(i = /text{prime}/) 的概率会更大，枚举范围也减少了。

因此，我们可以直接枚举 /(i = 6c/) 满足 /(c /ge 1/)，检验 /((i-1)/) 与 /((i+1)/) 即可。

注意，枚举时，方法二的技巧仍然要使用。

时间复杂度是 /(O(/dfrac{/sqrt{n}}{3})/)，但是这玩意约是 /(O(/sqrt[3]{n})/)。

bool isp(int x)
{
	if (x <= 1) return false;
	if (x == 2 || x == 3) return true;
	if (x % 6 != 1 && x % 6 != 5) return false;
	for (int i = 6; i*i <= x; i += 6)
		if (x % (i-1) == 0 || x % (i+1) == 0)
			return false;
	return true;
}

由于码量不会多多少，所以考试用这种优化方法是有好处的。

时间测试

给大家普及一波测时间的办法：

首先需要头文件 #include <ctime>。

然后，主要格式如下（原理大家一看就懂）：

int cl = clock(); //获取当前时间。
/*然后在此处写下你要测试的内容。*/
int cl = clock() - cl; //用当前时间 减去 开始时间。
cout << cl; //输出就是算法时间了（注意，单位为 ms）。

代码贴剪贴板里了，请自行查看。

这边给出测试结果：

n = 1e5
isp1: 1294.
isp2: 16.
isp3: 0.

可以看出：第一种办法慢过头了，第二种办法已经很快了，第三种直接秒杀。

由于方法一过于慢，我们只对比后两种办法。如下。

n = 1e7
isp1: 太慢了
isp2: 5322. (5s)
isp3: 1467. (1s)

哇噻！太厉害了！！！

结语 & 参考链接

内容参考这两篇博客：

1. 主要参考：https://blog.csdn.net/huang_miao_xin/article/details/51331710
2. 辅助理解：https://blog.csdn.net/Look_star/article/details/109190923

只不过是加上了个人理解与 /(/LaTeX/) 整理罢了。

希望能帮助大家卡常！

首发：2022-07-01 08:49:06