Pythonで素数のリストを作ろう
こんにちは。今年もあと10日ちょっとになってしまいました。
年賀状書きました？ 私はこれからです。
素数大富豪って何？
ネットで面白そうなものを見つけたんですよ。
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]
素数のリストを返すという最低限の目標はとりあえずクリア。
エラトステネスのふるいをコード化すると
他の方が書いてくださったコードを引用しました。
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 秒
