素数判定アルゴリズムについて

Pythonによる素数判定アルゴリズム

用語定義

• 自然数：1以上の整数
• 素数：約数が1とその数自身である自然数
  • ただし、1は素数でない。
• 合成数：素数でない数

素数判定アルゴリズム

素数であることの定義は、約数が1とその数自身である自然数である。

アルゴリズムの1つは、ある自然数Zを２からZまで割っていき、Zで割ったとき以外、一度も余りが0にならなければ素数と判定するものである。

以下の2点を踏まえてアルゴリズムを実装した。

• ZをZで割った余りは0であることは明らかなので、２からZ-1でよい。
• 加えて、隣り合う自然数は互いに素であるから、Z-1では余りが0にならない。したがって、Z-2でよい。

isPrime.py

def isPrime(Z):
    if Z < 2:
        return False
    else:
        for i in range(2, Z-1):
            if Z % i == 0:
                return False
        return True  

しかし、この方法は総当たりで、Zが大きくなるにつれて、計算量が膨大になる。したがって、より良いやり方を2つ目に提示する。

2つ目のアルゴリズム

2つ目のアルゴリズムには、「合成数aは、b<=√a を満たす素因数bをもつ」という性質を利用する。

証明：

合成数は、少なくとも二つ以上の素数の積で構成されている。合成数をN、素数をp,qとおくと、
N>=p＊q　-①
である。ここで、√N<pかつ√N<qと仮定すると、
N<pq
となり、①に反する。したがって、N>√pまたはN>√qである。

以上のことから、Nは√N以下に少なくとも１つ素数が存在していることが分かる。よって2からz-1まで調べず、√Nまで調べれば十分である。

また、計算量を下げるための工夫を２つ施す。

• Nが2の倍数か判定
  Nが2の倍数か判定することで、計算量を半分にできる。

• iの初期値を3にする
  iの初期値を3にすることで、i+=1ではなくi+=2とできる。なぜなら、4以上の偶数は素数でないことが確定しているからである。そのため、初めにNが2であるかどうかを判定している。

以上を踏まえ、より良いアルゴリズムは以下のとおりである。

isPrime1.py

def isPrime1(N):
    if N == 2:
      return True
    if N < 2 or N % 2 == 0:
      return False
    i = 3
    while i**2 <= N:
        if N % i == 0:
          return False
        i += 2
    return True