判断质数的方式

介绍

一个大于1的自然数，除了1和他本身以外，不能被其他自然数（质数）整除（2,3,57等），就是该数除了1和他自身以外都没有其他的因数

算法一

针对输入的数字x，我们可以遍历从2到x-1这个区间中的数，如果x能被这个区间中任意一个数整除，那么它就不是质数。

def is_prime1(x):
    for i in range(2, x):
        if num % i == 0:
            return False
    return True

算法二

对算法一的优化，事实上只需要遍历从2到√x即可。

def is_prime2(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True

算法三

偶数中除了2都不是质数，且奇数的因数也没有偶数，因此可以进一步优化。

def is_prime3(x):
    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False
    return True

算法四

任何一个自然数，总可以表示成以下六种形式之一：6n，6n+1，6n+2，6n+3，6n+4，6n+5（n=0,1,2...）我们可以发现，除了2和3，只有形如6n+1和6n+5的数有可能是质数。且形如6n+1和6n+5的数如果不是质数，它们的因数也会含有形如6n+1或者6n+5的数，因此可以得到如下算法：

def is_prime4(x):
    if (x == 2) or (x == 3):
        return True
    if (x % 6 != 1) and (x % 6 != 5):
        return False
    for i in range(5, int(x ** 0.5) + 1, 6):
        if (x % i == 0) or (x % (i + 2) == 0):
            return False
    return True