什么是质数？

质数（又称素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。例如：2, 3, 5, 7, 11等。质数在密码学、计算机科学和数学中都有重要应用。

本教程将介绍在Python中处理质数的多种方法，包括：

• 判断一个数是否为质数
• 生成质数列表的高效算法
• 质因数分解
• 实际应用场景

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

# 测试示例
print(is_prime_basic(17))  # 输出: True
print(is_prime_basic(25))  # 输出: False

import math

def is_prime_optimized(n):
    if n <= 1:
        return False
    if n == 2:  # 2是唯一的偶数质数
        return True
    if n % 2 == 0:  # 排除偶数
        return False
        
    # 只需检查奇数因子到平方根
    sqrt_n = math.isqrt(n)
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

# 测试大质数
print(is_prime_optimized(10000019))  # 输出: True

性能对比: 对于大数n，优化方法比基础方法快数千倍！

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # 将i的倍数标记为非质数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
                
    # 收集所有质数
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

# 生成100以内的质数
primes_under_100 = sieve_of_eratosthenes(100)
print(primes_under_100)  # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def prime_factors(n):
    factors = []
    # 处理2的因子
    while n % 2 == 0:
        factors.append(2)
        n //= 2
        
    # 处理奇数因子
    f = 3
    while f * f <= n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
            
    # 如果剩余的是质数
    if n > 1:
        factors.append(n)
        
    return factors

# 分解数字100
print(prime_factors(100))  # 输出: [2, 2, 5, 5]
# 分解大数
print(prime_factors(999999))  # 输出: [3, 3, 3, 7, 11, 13, 37]

1. 密码学

RSA加密算法基于大质数分解的困难性，使用两个大质数的乘积作为公钥的一部分。

2. 散列函数

许多散列函数使用质数来减少碰撞，例如在除法散列法中，选择质数作为表大小。

3. 随机数生成

线性同余生成器（LCG）中，模数通常选择为质数以获得更长的周期。

4. 算法优化

在需要循环或周期性操作的场景中，质数长度可以避免重复模式。

总结

在Python中处理质数时：

1. 判断单个质数：使用优化试除法（检查到√n）
2. 生成质数列表：使用埃拉托斯特尼筛法
3. 质因数分解：结合除法和试除法的思想

掌握这些算法将帮助您在算法竞赛、密码学项目和数学应用中高效处理质数相关问题。