首页 › Python 实例 › 输出指定范围内的质数

Python 输出指定范围内的质数

数学实例 011

题目

使用埃拉托斯特尼筛法找出 100 以内的所有质数。

参考代码

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [i for i, flag in enumerate(is_prime) if flag]

primes = sieve(100)
print(f"100 以内共有 {len(primes)} 个质数:")
for i in range(0, len(primes), 10):
    print(" ".join(f"{p:>3}" for p in primes[i:i + 10]))
执行以上代码输出结果为:
100 以内共有 25 个质数:
  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

代码解析

筛法的思路是从 2 开始,把每个质数的倍数都标记为合数,剩下没被标记的就是质数。它比逐个判断快得多,适合一次性求出某个范围内的全部质数。