素数判断算法优化与GESP考试实战

1. 项目背景与需求解析

素数判断是编程竞赛和算法学习中的经典问题，也是GESP（青少年编程能力等级考试）2级考试中的常见题型。2023年6月的这道"找素数"题目，主要考察考生对循环结构、条件判断和基础数学知识的掌握程度。

在实际编程中，素数判断的应用场景非常广泛：

• 密码学领域（如RSA加密算法的基础）
• 哈希表大小选择
• 随机数生成器设计
• 算法优化中的质因数分解

这道题目的典型要求是：给定一个正整数n，找出所有小于等于n的素数。看似简单，但其中蕴含着多个需要仔细处理的细节和优化点。

2. 基础算法实现

2.1 暴力判断法

最直观的方法是逐个判断每个数是否为素数：

python复制def is_prime(num):
    if num < 2:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

def find_primes(n):
    primes = []
    for num in range(2, n+1):
        if is_prime(num):
            primes.append(num)
    return primes

注意：这里需要特别处理1和0的情况，因为它们不被认为是素数

2.2 优化思路分析

暴力法虽然简单，但效率较低。我们可以从数学角度进行优化：

1. 范围缩小：只需要检查到√n即可，因为如果n有大于√n的因数，那么它必然有一个小于√n的对应因数
2. 偶数排除：除了2，所有偶数都不是素数，可以跳过
3. 预筛选：使用埃拉托斯特尼筛法（筛法）可以更高效地找出素数

3. 算法优化实现

3.1 平方根优化法

改进后的素数判断函数：

python复制import math

def is_prime_optimized(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num %