找质数最佳方法（质数判断最简单方法）

1.

方法一：

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

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

2.

方法二：

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

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

3.

方法三：

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

4.

方法四：

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

为什么？

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