見出し画像

[Python] #5 素数と学ぶ Python: エラトステネスのふるい

Kimono club

概要　素数はおもしろい性質をもっています。素数をテーマにプログラミングを楽しく学んでいきましょう。

前回の復習

前回，100000までの素数の個数を数え上げることに挑戦しました。0.08秒でおわりました。しかし，もっとはやいコードは書けないでしょうか。今回は，エラトステネスのふるいというアルゴリズムを使って，効率化を進めてみましょう。コードの無駄をより省く

エラトステネスのふるい

エラトステネスのふるいは、古代ギリシャのエラトステネスが考案した素数を見つけるための方法です。以下の手順で計算します。

  1. 数のリストを作る: 2から指定した数までの自然数を順番に並べたリストを作る。

  2. ふるいにかける:

    • まず、2は素数なので残します。

    • 次に、2の倍数（4, 6, 8, ...）をリストから取り除きます。

    • 次に、残った数の中で一番小さい3は素数なので残します。

    • 3の倍数（6, 9, 12, ...）をリストから取り除きます。

    • これを繰り返します。

  3. 素数を見つける: 最後にリストに残った数が素数です。

エラトステネスのふるいは、順番に倍数を取り除いていき，素数でない数をふるい落としていく方法です。ふるい落とされなかった数は，どの数の倍数でもない数、つまり素数というわけです。

コードにしてみよう

1. 数のリストを作る

import time
import math

start = time.time()

limit = 10**5 + 1
sieve = [True] * limit
sieve[0] = sieve[1] = False

for i in range(2, int(math.sqrt(limit)) + 1):
    if sieve[i]:
        for j in range(i*i, limit, i):
            sieve[j] = False

primes = [i for i, is_prime in enumerate(sieve) if is_prime]

prime_counts = {}
count = 0
for i in range(2, limit):
    if sieve[i]:
        count += 1
    if i in [10**n for n in range(1, 6)]:
        prime_counts[i] = count

for n in range(1, 6):
    print(f"10^{n}\tまでには{prime_counts[10**n]}個")

end = time.time()
time_diff = end - start
print(time_diff)

エラトステネスのふるいを作って1億までの素数の個数を数え上げるコードです。

エラトステネスのふるいを説明していきましょう。このアルゴリズムで最初にすることは，数のリストを作るところからはじまります。対応するコードを再掲します。

limit = 10**5 + 1
sieve = [True] * limit
sieve[0] = sieve[1] = False

１行目，変数 limit に100001を代入しています。10**5  は 10 の5乗のことです。

２行目，変数 sieve はリストを代入しています。

リストは、複数の要素を順番に格納できます。リストは、角括弧[]の中に要素をカンマで区切って記述します。

sieve = [True]

上の例でいうと，角括弧 [] の中に True がひとつ入っていることを表しています。

sieve = [True] * limit

[True] * limit は，True が limit 分は言っているリストを作って欲しいというコードです。

sieve = [True, True, True, True, True, 
         True, True, True, True, True, 
         True, True, True, True, True, 
         ..., True ]

３行目，sieve[0] = sieve[1] = False はリストの0番目と1番目に False を代入しています。

sieve[0] = sieve[1] = False

sieve[0] と sieve[1] の値は上の例では False になっています。

 2. ふるいにかける

対応するコードを再掲します。

for i in range(2, int(math.sqrt(limit)) + 1):
    if sieve[i]:
        for j in range(i*i, limit, i):
            sieve[j] = False

１行目，2で始まり10億１の平方根に1を加えた数までの整数の範囲を生成し，変数i に2, 3, 4, と入れていき繰り返していきます。

２行目，sieve[2] が True だったら，３行目以降の処理をします。ここで sieve[2]がTrue であることは整数 2 が素数であることを表しています。

３行目，$${i \times i}$$ から開始し，i 個間隔で，limit までの数の範囲を生成します。i が 2の場合，具体的には 4, 6, 8, 10, 12, 14,… という数の範囲が生成されます。 

４行目，生成した範囲にある数が素数ではないと指定しています。

実行してみよう

実行してみると，0.07秒でおわりました。前回のコードでは 0.08秒でしたので，すこし改善されました。

10^1	までには4個
10^2	までには25個
10^3	までには168個
10^4	までには1229個
10^5	までには9592個
0.07490205764770508

今回作ったコードにはまだ無駄があります。10行目のfor i in range(2, int(math.sqrt(limit)) + 1):という箇所です。sieve[] の2, 3, 4, 5, 6,… 番目が True か False かを以降確認するために，2, 3, 4, 5, 6, …  という数の集まりを生成しています。しかし，偶数は素数ではないですから，こんなにたくさんの数を生成する必要はないでしょう。どうすればいいでしょうか。次回までに考えておいてください。

次回の予告

次回はエラトステネスのふるいのコードをより効率化する方法について考えていきます。

関連する記事

以前作ったパズルゲームです。面白いと思います。

  • 解ける？Python with Pyxel でパズルゲームを作りました。[note]

およそ1年前ピンポンを作ろうと思ってそのままになっていました。また続きを書いてみたいです。

  • ピンポンを Python with Pyxel で作る。[note]

Python のおすすめの入門書

[ サイトマップを見る ]


いいなと思ったら応援しよう！