[python] 自然数N以下の素数をすべて求める

はじめに

素数に関するアルゴリズム問題は定番なので、少し勉強した

問題

自然数N以下のすべての素数を求めよ

Code

from typing import List


def generate_primes(number: int) -> List[int]:

    # 素数
    primes = []

    # for文の作業を減らすために、cahceで繰り返しを減らす
    cache = {}

    for x in range(2, number + 1):
        is_prime = cache.get(x)
        if is_prime is False:
            continue

        # 素数である
        primes.append(x)
        cache[x] = True

        # x の倍数はすべて素数ではないので、cacheのFalseとして処理
        for y in range(x*2, number+1, x):
            cache[y] = False

    return primes

結果

print(generate_primes(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]

感想

二重for文でアルゴリズム問題を解けなかったことが多かったが、dicでcacheを利用することによって時間・作業の短縮ができることを初めて知った