素数表を作るシンプルなスクリプト

引数で渡された数までの素数表を作る python スクリプト prime.py を書いた。できるだけ少ない行数にしたかったのでちょっと見づらいかもしれない。というか見づらい。

from typing import List
import sys

max: int
try: max = int(sys.argv[1])
except: max = 1000

def make_prime_table(max: int) -> List[int]:
  prime_table: List[int] = [2]
  for value in range(3, max + 1, 2):
    if is_prime(value, prime_table):
      prime_table.append(value)
  return prime_table

def is_prime(value: int, prime_table: List[int]) -> bool:
  for p in prime_table:
    if value % p == 0: return False
    if p * p > value: return True
  return False

print(make_prime_table(max))

1 - 6: 引数処理。判定の終点を max とする。
8 - 13: 素数表作成の関数。
9: まず余計な判定処理を減らすために初期状態の素数リストでは最初の素数 2 をあらかじめセットしておく。
10: 判定対象である 3〜引数までのループ。奇数であることは確定しているので step 2 で回している。
11: 素数判定。
12: 素数だったらテーブルに加える。
15 - 19: 素数判定の関数。
16: 素数表の素数でループする。
17: 引数が素数表の素数で割り切れたら（value % p == 0）素数ではない。
18: 割る素数が √value を超えたらその先は試す必要がないので、素数であることが確定する。３以上の整数 n では √n < n - 1 なので直前までの素数表には判定に必要な素数がすべて含まれている。
19: 形式上の return。ここに来ることはないはず。
21: 素数表作成実行。
22: 結果表示。

私は python についてはまったくの初心者なので、上のコードは python らしい書き方ではないかもしれないし、全体的にエラー処理が甘い。

ポイントは素数テーブルを作りながら、素数判定に利用していること。関数 is_prime は判定対象の平方根値よりも小さい素数が網羅された素数テーブルを持っていることを前提とした素数表を作るための判定だ。そのため素数表の作成を目的としない素数判定処理にはそのままでは使えない。

たとえば「素数表とかどうでもいいから 4999999 は素数であるかを知りたい」のであれば、√4999999 ≒ 2236 なので、まず
make_prime_table(2236, prime_table) で 2236 までの素数表を作って is_prime(4999999, prime_table) で判定する必要がある。これが効率が良い方法であるかどうかは分からない。もっとシンプルな方法があるかもしれない。

python は Windows でも mac でもただで使えるので、インストールして DOS 窓とかターミナルで 

python prime.py 10000

とか打てば実行可能なはず（python を使ったことがない人がここまで読んでるとは思えないが）。10000 は素数表の上限値。私の環境だとゼロが7 つあたりで動作が急激に遅くなった。