python计算质数的6种方法

下面就详细讲解“Python计算质数的6种方法”的完整攻略。

1. 前言

算法是计算机科学中非常重要的一个领域，而质数计算是其中一个经典问题。Python是一种强大的编程语言，注重可读性和简洁性，因此特别适合用来解决这样的算法问题。在本篇攻略中，我们将介绍Python计算质数的6种方法。

2. 六种方法

方法一：暴力枚举法

该方法是最基本的算法之一。我们从2到n-1枚举所有数，判断是否能被n整除，如果不能则n为质数。

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

方法二：优化后的暴力枚举法

暴力枚举法虽然简单，但对于大整数计算效率低下。通过数学原理，我们可以剪枝优化该算法，即只需要枚举2到n的平方根即可。

import math

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

方法三：埃氏筛法（欧拉筛）

该算法利用质数的特性，从2开始，将每个质数的倍数都标记为合数。通过枚举时跳过非质数，从而减少计算量。该算法的时间复杂度为O(nlog(logn))。

def eratosthenes(n):
    if n < 2:
        return []
    prime = [True]*(n+1)
    prime[0] = False
    prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    return [x for x in range(2, n+1) if prime[x]]

方法四：线性筛法

该算法利用了双重循环遍历质数和合数的特性，实现了优秀的时间复杂度。其基本思想是将每个合数分解成两个数的乘积，例如12=26或34，其中较小的因子一定已经遍历过。该算法的时间复杂度为O(n)。

def sieve(n):
    if n < 2:
        return []
    prime = [True]*n
    primes = []
    for i in range(2, n):
        if prime[i]:
            primes.append(i)
        for j in range(len(primes)):
            if i*primes[j] >= n:
                break
            prime[i*primes[j]] = False
            if i % primes[j] == 0:
                break
    return primes

方法五：试除法

该方法与暴力枚举法类似，但只需要从2到n的平方根进行枚举，同时如果n不能被2整除则只需枚举奇数，从而减少计算量。该算法的时间复杂度为O(n^0.5)。

def trial_division(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

方法六：费马小定理

该方法基于一个数学定理，如果p是质数且a是不被p整除的任意整数，那么a^(p-1) - 1被p整除。该定理通过逆否命题可用于检测质数，但计算过程中需要使用到高次幂的计算，因此暴力枚举法在小范围内依旧是最快的（在实际生产环境中，更多使用碰撞检测算法进行质数判断）。以下为该方法的Python代码示例：

def is_prime_fermat(n, k=5):
    if n < 2:
        return False
    for _ in range(k):
        a = random.randint(2, n-1)
        if pow(a, n-1, n) != 1:
            return False
    return True

3. 总结

在本篇攻略中，我们介绍了Python计算质数的6种方法，并给出了每种方法的Python代码示例。这些方法都在不同的方面做了优化，具有各自的优缺点，可以根据具体的使用场景进行选择。希望读者可以通过本篇攻略了解到Python算法优化的一些基本思路。