ひたすら素数を生成するプログラムを書いてみた

アタマの体操がてら、ひたすら素数を生成するプログラムを書いてみた。

Source

prime_num.py

import math
import sys

def check(num, prime_num):
    index = 0
    if not prime_num:
        prime_num = [2]
    min_factor = prime_num[index]
    max_factor = math.floor(math.sqrt(num))
    while min_factor <= max_factor:
        remainder_big = num % max_factor
        remainder_small = num % min_factor
        if remainder_big == 0 or remainder_small == 0:
            return False
        else:
            index += 1
            min_factor = prime_num[index]
            temp = num / min_factor
            if temp <= max_factor:
                max_factor = math.floor(temp)
            else:
                max_factor -= 1
    return True

num = 2
prime_num = list()
max = int(sys.argv[1])
while num <= max:
    if check(num, prime_num):
        prime_num.append(num)
    num += 1
for i in prime_num:
    print(i)

仕様

単純にひたすら総当りで計算しても良いのだが、計算を効率化するためにいくつか改善点を導入した。

• ある値の最大の約数は平方根までになるので、それ以上の値は検証しないようにした。
• ある値を検証する際、小さい方と平方根を上限とする大きい方の両側から検証して、検証する値を小さい方の値で割った値を上限に更新していくことで検査する約数のレンジを絞り込むようにした。
• 合成数(非素数)を用いて検証する必要はない(合成数の約数で割り切れるのは明らかだから)ので、これまで生成した素数をListに格納して、それを用いて検証するようにした。

実行速度

$ date && pypy3 prime_num.py 10000000 >/dev/null && date
2022年  8月 23日 火曜日 17:51:48 JST
2022年  8月 23日 火曜日 17:52:04 JST

Pypy使えば、1000万以下の素数を全てリストアップするのに16秒くらい。けっこう速い。
以前に同じようなコードを書いたときには同じマシンで53秒かかっていたみたいだから、だいぶ高速化できた。