python怎么判断是否为质数

  • Post category:Python

给出一个正整数n,如何判断它是否为质数(素数)呢?

一般地,我们都知道,如果一个数如果不是质数,那么它必然可以表示为两个自然数的乘积:$n = a*b$。而其中的一个数必然小于等于 $\sqrt{n}$,另一个数必然大于等于 $\sqrt{n}$。因此,我们只需要判断 n 是否能被 $2\sim \sqrt{n}$ 中的任意一个正整数整除即可。

以下是两个Python实现,第一个使用循环,第二个使用函数递归:

方法一:循环判断是否为质数

def is_prime(n):
    if n <= 1:
        return False

    # 判断是否可被 2 整除
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    # 循环判断大于 2 的奇数是否能被整除
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

方法二:递归判断是否为质数

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    return is_prime_recursive(n, 3)  # 从3开始循环判断是否为质数

def is_prime_recursive(n, i):
    """
    递归判断是否为质数
    """
    if i * i > n:
        return True
    if n % i == 0:
        return False
    return is_prime_recursive(n, i + 2)

在这里,我们为了避免重复代码,使用了递归函数判断 $n$ 是否为奇数,因为在循环中 $i$ 从 $3$ 开始,每次加 $2$,因此我们在递归函数中也从 $3$ 开始,每次加 $2$。

注意,以上两个函数均可以识别负数和小数,并且处理了 0 和 1 的情况。

在实际应用中,我们也可以使用埃拉托色尼(Sieve of Eratosthenes)算法和欧拉筛法(Sieve of Euler)等方法来判断质数。