Pythonで素数生成プログラムを作ってみた

発想

ある自然数について、それより小さい素数で割り切れなければ、その自然数は素数である。

という発想でプログラムを書いてみました。

あるリストを用意しておいて、素数をつぎつぎとそのリストに保存していきました。

コード

import time

primes_list = []          # このリストに素数を保存していく
upper_lim   = 10000       # テキトーな数を設定
start_time  = time.time() # 開始時刻を記録

for integer in range(2, upper_lim + 1, 1): # 2-10000の整数に対して、
    if len(primes_list) < 1 :              # primes_listが空だったら、
        primes_list.append(integer)        # primes_listにinteger(=2)を追加する
    else:                                  # その他の場合（本題）、
        is_divisible = False               # integerが割り切れない、つまり素数であることを仮定する
        for prime in primes_list:          # 今までに保存された全ての素数"prime"について、
            if integer % prime == 0:       # integerがprimeで割り切れるならば
                is_divisible = True        # 割り切れます（つまり素数じゃない）
                break                      # そしたらもうこのforはやる意味がないです。
        # integerが合成数ならどっかのprimeでis_divisible = Trueになる
        if not is_divisible:               # すべてのprimeについてこの判定をしたのち、それでもなおis_divisible = Falseならばもうそれは素数
            primes_list.append(integer)    # integerを素数として認め、primes_listに追加する

print(primes_list)
print(len(primes_list), "prime numbers foud.")

elapsed_time = time.time() - start_time # 経過時間 = 現在時刻 - 開始時刻
print ("run time: {0}".format(elapsed_time) + " seconds")

出力：

$ python prime_numbers.py
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 

（...省略...）

9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
1229 prime numbers foud.
run time: 0.0615689754486084 seconds

実行時間について

• $10^2$まで探索: 0.0001 sくらい
• $10^3$まで探索: 0.001 sくらい
• $10^4$まで探索: 0.06 sくらい
• $10^5$まで探索: 4 sくらい
• $10^6$まで探索: 240 s = 4 minくらい
• $10^7$以降: ??? 数時間くらい？

環境は

• MacBook Pro (13-inch, 2019, Four Thunderbolt 3 ports)
• プロセッサ：2.4 GHz クアッドコアIntel Core i5
• メモリ：16 GB 2133 MHz LPDDR3

続く

Pythonで素数生成プログラムを作ってみた2