博客

python实现判断是否为素数的函数

  • Post category:Python

下面是Python实现判断素数的完整攻略：

一、什么是素数？

素数，又称质数，是指只能被 1 和自己本身整除的正整数。

二、判断素数的方法

判断素数的方法通常有两种：试除法和素数筛法。下面分别介绍这两种方法的实现。

1. 试除法

试除法是一种最基础的判断素数的方法，它的思路是从 2 到 $ \sqrt{n} $ （其中 n 是待判断的数），依次判断 n 能否被这些数整除。如果能被整除，那么 n 就不是素数。

下面是使用试除法判断素数的 Python 实现代码：

import math

def is_prime(n):
    """判断n是否为素数"""
    if n <= 1:
        return False
    # 判断n是否能被2到sqrt(n)之间的整数整除
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

上述代码中，首先判断 n 是否小于等于 1，如果是直接返回 False。然后使用 for 循环从 2 到 $ \sqrt{n} $ （注意这里一定要加 1，否则最后一个数是不会被取到的），依次判断 n 是否能被这些数整除。如果能被整除，那么 n 就不是素数，返回 False。如果能够遍历完整个循环，那么 n 就是素数，返回 True。

2. 素数筛法

素数筛法是一种更高效的判断素数的方法，常见的有埃氏筛法和欧拉筛法。这里我们介绍一下埃氏筛法的实现方法。

埃氏筛法的基本思想是，从 2 开始，将每个素数的倍数都标记成合数，依次遍历到 n，那么所有未被标记成合数的数就都是素数。

下面是使用埃氏筛法判断素数的 Python 实现代码：

def primes(n):
    """返回所有小于等于n的素数列表"""
    is_prime = [True] * (n + 1)  # 初始化is_prime数组，全部置为True
    primes = []  # 存放素数的列表
    for i in range(2, n+1):
        if is_prime[i]:  # 如果i是素数
            primes.append(i)  # 将i加入素数列表
            # 将i的倍数都标记成合数
            for j in range(i**2, n+1, i):
                is_prime[j] = False
    return primes

上述代码中，首先初始化一个 is_prime 数组，全部置为 True。然后从 2 开始遍历到 n，如果当前数 i 是素数（即 is_prime[i] 为 True），那么将 i 加入素数列表 primes 中，并将 i 的倍数都标记成合数。其中，将 i 的倍数都标记成合数的代码为：

for j in range(i**2, n+1, i):
    is_prime[j] = False

这里的 range() 函数的第一个参数为 i 的平方，因为小于 i 的倍数的数已经在之前被标记过了，所以从 i 的平方开始，每隔 i 个数标记一次。最后返回素数列表 primes 即可。

三、总结

以上就是使用 Python 实现判断素数的两种方法，试除法和素数筛法的具体实现过程。在实际使用中，可以根据输入数据的范围和具体的时间复杂度要求来选择使用哪种方法。

Tags: