Python 判断素数

什么是素数

素数又称质数，是指除了1和自身之外不能被其他数整除的整数。例如，2、3、5、7、11、13等都是素数。

对于一个给定的整数n，如果它大于1且不能被2到√n范围内的任意一个整数整除，则可以判断它是一个素数。

判断一个数是否为素数

在Python中，我们可以使用多种方法来判断一个数是否为素数。下面将介绍两种常见的方法。

方法一：暴力法

使用暴力法是一种最简单直接的方法来判断一个数是否为素数。它的思想是逐个检查从2到n-1范围内的每个整数，看是否能够整除给定的数。如果能够整除，则说明这个数不是素数；否则，这个数就是素数。

下面是使用暴力法判断一个数是否为素数的示例代码：

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

# 测试示例
print(is_prime(2))  # True
print(is_prime(5))  # True
print(is_prime(10)) # False
print(is_prime(15)) # False
print(is_prime(20)) # False

代码运行结果：

True
True
False
False
False

使用暴力法判断一个数是否为素数的时间复杂度为O(n)。

方法二：优化方法

在实际应用中，暴力法效率较低，不适用于大型数的判断。为了提高执行效率，我们可以使用优化方法。

优化思路1： 在暴力法的基础上，我们可以减少循环的次数。因为一个数n是否能被k整除，当且仅当 n = a * b时，a和b中至少有一个小于等于√n。所以，我们只需要判断从2到√n的范围即可。

下面是使用优化方法判断一个数是否为素数的示例代码：

import math

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

# 测试示例
print(is_prime(2))  # True
print(is_prime(5))  # True
print(is_prime(10)) # False
print(is_prime(15)) # False
print(is_prime(20)) # False

代码运行结果：

True
True
False
False
False

优化思路2： 在优化思路1的基础上，我们可以进一步减少循环的次数。因为在一个数n的因数中，除了1和n本身之外，不可能存在大于√n的因数。所以，我们只需要判断从2到√n的范围即可。

下面是使用进一步优化的方法判断一个数是否为素数的示例代码：

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

# 测试示例
print(is_prime(2))  # True
print(is_prime(5))  # True
print(is_prime(10)) # False
print(is_prime(15)) # False
print(is_prime(20)) # False

代码运行结果：