当前位置：首页 > Python > 正文

Python生成质数列表的完整教程 - 从基础到高效算法

XuYueTi
Python
2025-07-27
605

Python生成质数列表的完整教程

学习多种方法生成质数列表，从基础实现到高效算法

什么是质数？

质数（素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。例如：2, 3, 5, 7, 11, 13等。

在本教程中，我们将学习使用Python生成质数列表的多种方法，包括：

基本循环方法
优化后的质数判断
高效的埃拉托斯特尼筛法
使用Python内置函数的简洁方法

方法1：基本循环方法

这是最直接的实现方式：遍历每个数字，检查它是否为质数。

def generate_primes_basic(n):
    primes = []
    for num in range(2, n+1):
        # 检查num是否为质数
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

# 生成100以内的质数
print(generate_primes_basic(100))

方法分析：

优点：逻辑简单，易于理解
缺点：效率较低，时间复杂度为O(n²)
适用场景：小范围数字（n < 10,000）

方法2：优化后的质数判断

通过数学优化提高效率：只需检查到平方根，跳过偶数。

import math

def is_prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    # 只需检查到平方根
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

def generate_primes_optimized(n):
    primes = [2] if n >= 2 else []
    # 只检查奇数
    for num in range(3, n+1, 2):
        if is_prime(num):
            primes.append(num)
    return primes

# 生成1000以内的质数
print(generate_primes_optimized(1000))

方法分析：

优化点1：跳过偶数（2除外）
优化点2：只需检查到平方根
效率提升：比基本方法快10-100倍
适用场景：中等范围数字（n < 1,000,000）

方法3：埃拉托斯特尼筛法

最著名的高效质数生成算法，时间复杂度为O(n log log n)。

def sieve_of_eratosthenes(n):
    # 创建标记列表，初始都为True
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    
    # 从2开始到平方根
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # 标记所有p的倍数为False
            for i in range(p * p, n+1, p):
                is_prime[i] = False
        p += 1
    
    # 收集所有质数
    primes = [i for i in range(2, n+1) if is_prime[i]]
    return primes

# 生成1,000,000以内的质数
primes = sieve_of_eratosthenes(1000000)
print(f"共找到 {len(primes)} 个质数")

方法分析：

优点：效率极高，特别适合生成大量质数
算法思想：排除法，标记非质数
时间复杂度：O(n log log n)
适用场景：大范围数字（n > 1,000,000）

方法4：使用Python内置函数

使用Python的filter和itertools模块创建简洁实现。

import itertools

def generate_primes_functional(n):
    # 使用filter和lambda函数
    return list(filter(lambda x: all(x % i != 0 for i in range(2, int(x**0.5)+1)), 
                    range(2, n+1)))

# 使用itertools生成无限质数序列
def infinite_primes():
    numbers = itertools.count(2)
    while True:
        prime = next(numbers)
        yield prime
        numbers = filter(lambda x, p=prime: x % p != 0, numbers)

# 获取前100个质数
primes = []
prime_gen = infinite_primes()
for _ in range(100):
    primes.append(next(prime_gen))
print(primes)

方法分析：

优点：代码简洁，函数式编程风格
缺点：效率不如筛法
特点：可以生成无限质数序列
适用场景：小规模需求或教学演示

方法比较与总结

方法	时间复杂度	空间复杂度	适用场景
基本循环	O(n²)	O(1)	n < 10,000
优化判断	O(n√n)	O(1)	n < 1,000,000
埃氏筛法	O(n log log n)	O(n)	n > 1,000,000
函数式方法	O(n²)	O(1)	教学/小规模