【Python】素数を判別するプログラムを実装する

ふと、素数を求めたくなったので素数を求めるアルゴリズムを実装してみます。 素数を判定する手法は色々とあるのでそれぞれ試してみます。

言語はPython3.6です。

ここでは10000までの素数を求めていきます。

Contents

• 素数　(Prime number)
• 判別方① 2からn-1まで割ってみる
• 計算回数を減らす　n-1までの奇数で割ってみる
• さらに減らす $\sqrt{n}$
• もっと減らす 素数のリストを使う
• 終わりに
• 参考
• 書籍

素数　(Prime number)

素数（そすう）とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。

Wiki

約数とはその数を割り切れる整数です。 つまり、１とその数以外の整数で割り切れてしまう数は素数ではありません。 ２以外の偶数だと、２で割り切れるためすぐに素数でないとわかりますね。

また、素数でない値は合成数(Composite number)と呼び、自然数で1とその数自身以外の約数を持つ数と定義されます。

判別方① 2からn-1まで割ってみる

単純にnが素数かどうか判別するのであれば、2からn-1までの数値で割ってみるのが良い。 割り切れたら素数ではない、割り切れなかったら素数です。 2は素数ですので先に判定する。

def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

if __name__ == "__main__":
    while True:
      n = int(input().strip())
      if isPrime(n):
        print(n, 'is prime number')
      else:
        print(n, 'is composite number')

出力

2
2 is prime number
12
12 is composite number
1533
1533 is composite number
97
97 is prime number

main関数は入力を受付けて素数か素数でないかを出力している。 isPrime(n)で受け取った数値を素数か判定している。

以下isPrime(n)を改良していく。

計算回数を減らす　n-1までの奇数で割ってみる

このままでは最大n回の比較をすることになる。 nが大きいと計算速度が心配なので少し改良する。

まず、偶数は2で割れるので２以外の偶数で割ってみる必要がない。 よって割ってみる数も奇数だけで良い。 また、かけてnになる整数は最大$2/n$までです。

import math

def isPrime(n):
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    # ２ではない偶数は素数ではない
    return False

  # nの半分まで計算する範囲を絞る
  m = math.floor(n / 2) + 1
  for p in range(3, m, 2): # 奇数だけ計算する
      if n % p == 0:
        return False
  return True

math.floor()は少数桁を切り捨てます。 range(3, m, 2)の３番目の引数は加算する数値となります。 2を渡しているので3から2ずつ加算して奇数だけ計算するようにしました。

計算量が前のものに比べて$1/4$ぐらいになりました。

さらに減らす $\sqrt{n}$

2つの自然数をかけて24となる数の組をみてみます。

組のうち小さい方の最大は4です。 このとき、$4 < \sqrt{24} \fallingdotseq 4.90$となり、左側の小さい数字は$\sqrt{24}$よりも小さい。 素数かどうかは$\sqrt{n}$までの範囲の計算に絞ることができます。

import math


def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

math.sqrt(n)を使ってnの平方根を求めています。

これで、最初のものと比べ計算量が$1/{2 \sqrt{n}}$まで減りました。

もっと減らす 素数のリストを使う

上記の方法で121を判定すると、3, 5, 7, 9, 11と割っています。 この時、9は3の倍数なので判定には無意味な数となってしまいます。

そこで、素数だけ割っていけば計算回数が少なくなることがわかります。 最初に素数を計算する必要がありますが、なんども判定するのであれば計算資源の節約になります。

# 素数のリスト
prime_numbers = [.....]

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  m = math.floor(math.sqrt(n))
  for p in prime_numbers:
      if n % p == 0:
        return False
      if p > m:
        # 素数がnの平方根を超えたら終了
        break
  return True

nは100,000,000までの数字として計算量を求めてみます。 $\sqrt{n}$までの素数がわかれば良いのです。 10,000までの素数は1,229個です。 最初に比べ$1229/100000000 = 1.229 \times 10^{-5}$まで減りました。

終わりに

10行程度のプログラムで素数を判定できました。 素数のリストを作成する方法は色々とあるので、またまとめたいと思います。

参考

• 素数判定いろいろ - シンプルな判定と、素数の分布

書籍

この本を読んで素数に思いを馳せました。 素数に出くわすと嬉しかったり、標本数が少ないと冷笑したり、パスタを茹でてベッセル関数を説明しだしたりと大変愉快な内容となっています。