博客

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）等方法来判断质数。

Tags: