求质数(素数)的几种方法

本文简单介绍几种判断一个数是否为质数的算法，并给出 Python 语言的实现。

质数的定义

质数又称素数，是一个大于1的自然数。该数只能被1和它自身整除
如果一个数不是质数，则称为合数。
0和1既不是质数也不是合数，最小的质数是2

完全枚举法

假设有大于一的自然数 n，要判定 n 是否为质数，则可以用大于1，小于n 的数顺位为 n 取余，只要其中有一个余数为零，则 n 为合数，如果都不为零，则 n 为质数。

代码实现如下:

def isPrime(num):
    if num <= 3:
        return num > 1
    ok = True
    for i in range(2, num):
        if num % i == 0:
            ok = False
            break
    return ok

改进方法

用上一种方法虽然可以正确得到结果，但如果 n 非常大，则枚举的数量也非常大(3 ~ n - 1), 非常低效，因此需要更高效的方法。根据数学理论，一个合数可以分解为两个非1的约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)，因此我们只需要判断在 3 ~ p1 的区间中是否有一个数可以整除n, 如果有，则n为合数，否则为质数。这样就把区间大大缩小了，比如要判断101 是否为质数，按照上一种方法，需要判断 99 次，而采用这种这种方法，只需要判断 9 次即可，大幅提高了效率。

实现代码如下:

def isPrime(num):
    if num <= 3:
        return num > 1
    num2 = round(num ** 0.5) # 平方根
    ok = True
    for i in range(2, num2 + 1):
        if num % i == 0:
            ok = False
            break
    return ok

继续改进

根据数学分析，质数还有一个提点: 就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

为直观的说明，我们先打印一下 100 以内的 6x - 1 和 6x + 1 的数来看看:

1	5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

我们在打印一下 100 以内的质数（为方便比较，只列出大于3的部分）

1	5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

可以看到，其中只有:

1	25, 35, 49, 55, 65, 77, 85, 91, 95

而这些数都是能被 6x -1 或 6x + 1 整除的。

根据以上特点，我们可以在前一个程序基础上继续优化，得到如下代码:

def isPrime(num):
    if num <= 3:
        return num > 1
    if num % 6 != 1 and num % 6 != 5:
        return False
    ok = True
    num2 = round(num ** 0.5)
    for i in range(5, num2 + 1, 6):
        if num % i == 0 or num % (i + 2) == 0:
            ok = False
            break
    return ok

那么这个算法判断 101 是否是质数需要判断几次呢？答案是 1 次，是不是效率大幅提高了。