首页 > 其他分享 >质数判定的常数优化

质数判定的常数优化

时间:2022-08-26 02:02:00浏览次数:99  
标签:int 质数 isp sqrt 枚举 判定 常数 bmod


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

如何迅速判断 \(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

标签:int,质数,isp,sqrt,枚举,判定,常数,bmod
From: https://www.cnblogs.com/liangbowen/p/16622892.html

相关文章

  • 判定字符是否唯一
    实现一个算法,确定一个字符串s的所有字符是否全都不同。示例1:输入s="leetcode"输出"false"示例二输入s="abc";输出"true"限制0<=len(s)<=100s[i]仅包......
  • leetcode1175-质数排列
    质数排列分别找出质数和合数的数量,将两者的阶乘相乘即可classSolution{publicintnumPrimeArrangements(intn){intcnt=0;for(inti=2;......