使用Python判断素数

介绍

素数是指除了1和本身以外，不能被其他正整数整除的数。判断一个数是否为素数，在计算机编程中非常常见。Python作为一门高级编程语言，也可以用来进行素数的判断。

判断素数的方法

试除法

试除法是最简单的一种方法，即判断一个数 n 是否为素数，只需在 2 到 n-1 的范围内判断 n 是否被整除。

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

质数倍数法

质数倍数法是一种非常有效的方法，可以处理较大的素数。它的基本思想是从 2 开始，不断将它的倍数标记为合数，直到所需要的素数都被找到，这种方法可以大大减少试除数的个数。

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

小标题

生成素数序列

可以通过生成素数序列的方式，找到所有小于等于给定值的素数。下面是利用试除法生成素数序列的代码：

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

这段代码利用一个布尔型列表 is_prime 记录每个数是否为素数。首先将 is_prime 中的每个元素置为 True，然后从 2 开始，在 range(2, int(n ** 0.5) + 1) 中循环，如果 is_prime[i] 为 True，那么将 i * 2、i * 3、i * 4 …… 等数全部标记为 False。

多重判断素数

为了判断一个大整数是否为素数，可以使用多重判断法，例如同余检验法、费马小定理等。其中，费马小定理的判断方式比较简单，可以用下面的代码实现：

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

总结

判断素数是计算机编程中的基本技能之一，Python提供了多种计算方式，包括试除法、质数倍数法、费马小定理等。如果要处理大的素数，可以使用更加高效的多重判断素数的方法。无论使用哪种方法，都需要注意处理好边界情况，以保证程序的正确性。