周回遅れでIT業界デビューしたエンジニアのブログ

就職氷河期にモロにぶち当たり、人生で混迷を極めた末にIT業界に安寧を見出そうとしているアラフォーのお勉強日記です。

Pythonで素数のリストを作ろう

こんにちは。今年もあと10日ちょっとになってしまいました。
年賀状書きました? 私はこれからです。

f:id:sionff:20180119162019j:plain

素数大富豪って何?

ネットで面白そうなものを見つけたんですよ。
www.ajimatics.com

「カードの切り方が素数」のトランプゲーム「大富豪」だとか。107なんかは10と7をくっつけて出したりできるとかで、数の大きな素数を知っていれば知っているほど有利になりそうな気配。

じゃぁどんな素数があるのか見てみよう

折角なのでコード書いてみました。とりあえずは予備知識なし、5分でぱぱっと作成。

# coding: utf-8

def predict_prime(n, x):
    for x_i in x:
        if n % x_i is 0:
            return x
        else:
            pass
    x = x + [n]
    return x

def makelist_prime(n):
    if n < 2: return []
    x = []
    for i in range(n):
        if i < 2 :
            pass
        else:
            x = predict_prime(i, x)
    return x

ans = makelist_prime(n)
print(ans)
# [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]

素数のリストを返すという最低限の目標はとりあえずクリア。

エラトステネスのふるい

ところで、素数を判別するのに有名な「エラトステネスのふるい」という方法があるそうで、調べてみました。Wikiが一番分かりやすかったのでぺたり。

エラトステネスの篩 - Wikipedia

以下の素数の性質を活かした方法。

  • 自然数nが√nを越えない最大の整数以下の全ての素数で割り切れなければ,nは素数である。
  • 素数は無限に存在する。
  • 任意の合成数は,ただ1通りの方法で素数の積の形に表すことができる。

エラトステネスのふるいをコード化すると

他の方が書いてくださったコードを引用しました。
qiita.com

# coding: utf-8
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

うーん、シンプルです。
私の書いたコードとは雲泥の差だ……!

性能を比べてみる

いい機会なので、こんな感じでそれぞれの時間を計測してみました。
100000までの素数をリスト化しています。

t1 = time.time()
n = 100000
primes(n)
t2 = time.time()
print("実行時間:", t2 - t1, "秒")

私のコードの実行結果

実行時間: 2.3438432216644287 秒

エラトステネスのふるいのコードの実行結果

実行時間: 0.015625 秒

……ははは……明日があるさ!(泣いてなんかない)

素数判別のロジックとコードの書き方(内包表記含む)で、これだけ差がつくことが良く分かったということで良しとしましょうそうしましょう。

素数大富豪、遊んでみたい!