萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網頁製作 >> HTML 腳本教學

Python 一行式篩選 100 以內質數:filter + lambda 函數式寫法

核心代碼

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)))
copyright © 萬盛學電腦網 all rights reserved