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 开始,把每个质数的倍数都标记为合数,剩下没被标记的就是质数。它比逐个判断快得多,适合一次性求出某个范围内的全部质数。