核心代碼
import math
def primes_upto(n):
"""返回 2..n 所有質數列表"""
return list(filter(
lambda x: not any(x % i == 0 for i in range(2, int(math.sqrt(x)) + 1)),
range(2, n + 1)
))
print(primes_upto(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]
邏輯解析
range(2, n+1) 生成候選數
filter(predicate, iterable) 保留滿足條件的元素
lambda x: not any(x%i==0 ...) 判斷無約數(即質數)
- 試除上限
sqrt(x),複雜度 O(√n)
優化版:埃拉托斯特尼篩法
def sieve(n):
"""O(n log log n) 篩法,大 n 時極快"""
is_prime = [True] * (n + 1)
is_prime[0:2] = [False, False]
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i, prime in enumerate(is_prime) if prime]
print(sieve(100)) # 同樣結果,百萬級毫秒級完成
生成器版(內存高效)
def prime_generator(limit):
yield 2
for num in range(3, limit + 1, 2):
if all(num % i for i in range(3, int(num**0.5) + 1, 2)):
yield num
print(list(prime_generator(100)))