「エラトステネスの篩」の高速な実装について #Pythonではじめるアルゴリズム入門

拙著『Pythonではじめるアルゴリズム入門』では「エラトステネスの篩」という有名なアルゴリズムを紹介しています。

Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量

「エラトステネスの篩」とは

「エラトステネスの篩」は、2で割り切れる数、3で割り切れる数、...というように、割り切れる数を順に除外する方法です。
これを繰り返すと、最終的に素数だけが残ります。

『Pythonではじめるアルゴリズム入門』より

この書籍の中では、上記の説明のように、篩にかけていく手順を解説しました。

高速な実装について

先日、@fujitanozomu様より高速な実装についてコメントいただきました。

Pythonで学ぶアルゴリズム　第4弾：素数 - Qiita

書籍ではページ数の都合もあり、掲載できませんので、ここに紹介させていただきます。
以下、いただいたコードの引用です。

def get_prime(n):
    sieve = [True] * (n + 1) 
    i = 2
    while i * i <= n: 
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False
        i += 1
    return [i for i in range(2, n + 1) if sieve[i]]  

コメントいただき、ありがとうございました。