当前位置:首页>维修大全>综合>

找质数最佳方法(质数判断最简单方法)

找质数最佳方法(质数判断最简单方法)

更新时间:2024-08-06 20:14:15

找质数最佳方法

1.

方法一:

要想知道x是不是质数,那就用它试着去除2~x-1,如果可以被整除,那就不是质数呗。

毫无疑问,这个算法效率是低到人难以忍受的。稍微优化一下,我们可以得到方法二。

2.

方法二:

第一个质数为2,那x只要是大于2的偶数就必然不是质数,这样我们就能排除掉一半的数了。对于奇数x,用它试着去除3、5...~x-2,如果可以被整除,那就不是质数。

计算效率高了一些,但算法复杂度本质上和第一种没什么区别,只是系数级的改进。

3.

方法三:

稍微思考一下就会发现,其实质数是分解质因数时只能分解成1和本身的数,既然如此,那么我们在试除的时候就没有必要从3、5一直除到x-2了,只需要除比自身小的质数就可以了。

4.

方法四:

再进一步思考就会发现,其实也没必要去试除所有比自身小的质数,只要试除比不大于自身的平方根的质数就可以了。

为什么?

假设x不是质数,那么它必然是最少两个质数的乘积,如果这两个质因数不相等,那么必然有一个质因数小于√x,如果两个质因数相等,那么这个质因数必然等于√x。

更多栏目