Pythonで素数を見つける方法: 試し割り法とエラトステネスの篩

pythonによる素数を求めるためのコードです。
自然数nが素数であるかどうかを判定する物ではないので注意してください

コード

1からnまでの素数の数を数えます。
メモリ容量によりますが、n = 10^7～9あたりが限界です。

試し割り法による素数判定

prime_numbers.py

import time

def is_prime(n):
    n += 1 # n = 1　からスタート
    if n <= 1: #1を除く
        return False
    for i in range(2, int(n**0.5) + 1): #素数の判定、2から初めてnの平方根まで計算する
        if n % i == 0: #試し割り
            return False
    return True

start = time.perf_counter() #計算時間の計測（スタート）
n = 10**6
primes = [i for i in range(n) if is_prime(i)]
end = time.perf_counter() #計算時間の計測（終了）
print('n:',n,'len:', len(primes), ' time:', end - start)
#n: 1000000 len: 78498  time: 6.511661022999988

エラトステネスの篩を用いて素数判定

Sieve_of_Eratosthenes.py

import time

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1) #リストの生成、全てTrue
    primes[0] = primes[1] = False #0と1は素数ではないので除外 FALSE
    for i in range(2, int(n**0.5) + 1):#2以上、2から初めてnの平方根まで計算する
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [i for i, is_prime in enumerate(primes) if is_prime]

start = time.perf_counter()
n = 10**6
primes = sieve_of_eratosthenes(n)
end = time.perf_counter()
print('n:',n,'len:', len(primes), ' time:', end - start)
#n: 1000000 len: 78498  time: 0.27198466100003316
#n: 1000000000 len: 50847534  time: 335.51925249500005

計算方法とコード実装の参考にしたサイト

素数の計算方法については以下のサイトを参考にしました。
高校数学の美しい物語

試し割り法やエラトステネスの篩の実装コードについては以下を参考にしました。
Pythonプログラムでの素数判定 - シンプル実装やエラトステネスの篩（ふるい）

感想

・試し割り法と比較して、nまでの自然数iの計算が1回しか行われない。計算量がとても少なく済む
・iに素数の判定がbool値による判定になるので高速。「計算しない」というのがスゴい
・試し割り法は除算を使うので遅くなる。四則演算のうち、加算・減算が最も早く、除算が最も遅い。
・n = 10**8あたりでメモリーの限界に到達。計算速度が極端に落ちた
・「1千万近いレコードをどう処理するか」というエンジニアとしての力量が問われる（気がする）。Fortranで微分方程式の計算に一晩かかった思い出が甦る。

その他

フリー版のGoogleColabで実行した際、試し割り法は10^7あたりで、エラトステネスの篩は10^9あたりでタイムアウトし実行結果を得られませんでした。

追記

試し割り法へ訂正

@koshi_waru さんからの指摘で、「割り出し」→「試し割り」へ訂正しました
試し割り法が正式な読み方でした。すいません。

コード訂正

試し割り法のコードに典型的なオフ・バイ・ワンエラーを含んでいました。
コード理解とテストが不十分でした。