Python 如何判断一个数是否为素数|极客教程

Python 如何判断一个数是否为素数

什么是素数

素数又叫质数，指大于1的自然数中，除了1和本身外没有其他因数的数。比如2、3、5、7、11等都是素数。

素数的特点

素数除了1和本身外没有其他因数，因此可以根据这个特点来判断一个数是否为素数。具体判断方法可以分为以下几种：

方法一：暴力法

最直接的方法就是遍历2到这个数的平方根之间的所有数，看是否有可以整除这个数的数。如果找到可以整除的数，那么这个数就不是素数，否则就是素数。

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

# 测试
num = 17
if is_prime(num):
    print(f"{num}是素数")
else:
    print(f"{num}不是素数")

运行结果为：

17是素数

方法二：素数定理

厄拉托斯特尼筛法，素数定理确定了n以内所有素数的一个上界，由此可以通过筛选法来判断一个数是否为素数。筛选法具体步骤如下：

创建一个长度为n+1的布尔数组prime_list，初始值都设置为True；
遍历2到n的平方根之间的所有数，如果某个数是素数，则将其倍数在数组中设置为False；
最终数组中仍然为True的数即为素数。

def is_prime(n):
    if n <= 1:
        return False
    prime_list = [True] * (n+1)
    for i in range(2, int(n**0.5)+1):
        if prime_list[i]:
            for j in range(i*i, n+1, i):
                prime_list[j] = False
    return prime_list[n]

# 测试
num = 17
if is_prime(num):
    print(f"{num}是素数")
else:
    print(f"{num}不是素数")

运行结果为：

17是素数

方法三：费马小定理

对于一个数n，费马小定理表明如果n是素数那么a^(n-1) ≡ 1 mod n，可以通过这个特性来判断一个数是否为素数。

def is_prime(n):
    if n <= 1:
        return False
    a = 2
    if pow(a, n-1, n) != 1:
        return False
    return True

# 测试
num = 17
if is_prime(num):
    print(f"{num}是素数")
else:
    print(f"{num}不是素数")