トップページ -> Pythonで数学をしてみよう！ -> Pythonで素数判定をしてみよう！

Pythonで素数判定をしてみよう！

今回は素数の判定をしてみたいと思います． 実はPython入門 基礎編でも触れたのですが，細かいことは気にしません． まずは簡単な問題から考えてみましょう．

課題

与えられた整数nが素数かどうかを判定したい．

まずは，考えてみてくださいね． 与えられた整数が約数を持たない 言い換えれば，2からn-1までの数で割り切れなければ素数ですね．

解法①


# 素朴な素数判定
import time
n = int(input())

start = time.time()
is_prime = True
for i in range(2,n):
    if n%i == 0:
        is_prime = False
        print(str(i) + "で割り切れる")
        break
    
elapsed_time = time.time() - start
print("elapsed_time:",elapsed_time)
print(is_prime)
まず，思いつくであろうやり方です． timeモジュールを使って時間を計測します． 2からn-1までの数で割ってみて割り切れたら素数でない 割り切れなければ素数というやり方です． プログラムの繰り返し処理の部分から最悪(nが素数)の場合，n-2回の割り算を行わないと結果が出ません．
1億回くらいの計算なら10秒程度で終わりますから，1億くらいまでの入力には10秒程度で対応できそうです． 入力が1桁増えると計算量も10倍になりますから単純計算で処理時間も10倍になります． 1000億くらいの素数になると日が暮れてしまいます． 無駄を省けないか考えてみましょう．
果たして，入力 n に対して n-1 で割り切れることがあるのでしょうか…？ 答えはnoです．2でない限り割り切れませんが繰り返し処理の書き方から2に関しては考える必要がありません． 入力 n に対して大きすぎる数で割ってみる意味がないことに気づきますね． どの程度までは省けるでしょうか？とりあえず，2を掛けたらnを超えてしまうような大きな数字は考慮する必要がないことはすぐわかります．

解法②


# ちょっと工夫した素数判定
import time
n = int(input())

start = time.time()
is_prime = True
# 2をかけたらnを超えるような数字は考慮しない
for i in range(2,n//2+1):
    if n%i == 0:
        is_prime = False
        print(str(i) + "で割り切れる")
        break
    
elapsed_time = time.time() - start
print("elapsed_time:",elapsed_time)
print(is_prime)
計算量が半分になったので処理時間もだいたい半分くらいになりましたね． さらに無駄を省くことはできないでしょうか？ この繰り返し処理の本質はよく考えると，2,3,5,7,11,13,… の倍数であるかどうかを判断するというところにあります． i=2が終わった時点でi=3に関しては既に2の倍数でないことが分かっているので3*3以上の数字に対してしか計算は意味を成しません． 同じようにある素数pについて考えると，2,3,5,…,pまでの計算をしている時点でp未満の素数を約数に持つことはありません． そのためnがp*p以上の数でなければ実行する意味がありません． 逆に考えれば(√n)*(√n)が考えられる最大の素数になります． √nが小数である場合を考慮して int(√n) まで計算しておけば素数判定が無駄なくできます． 計算量は√n程度です．

解法③


# 工夫した素数判定
import time
n = int(input())

start = time.time()
is_prime = True
# nが√nより大きい約数を持つことはない！
for i in range(2,int(n**0.5)+1):
    if n%i == 0:
        is_prime = False
        print(str(i) + "で割り切れる")
        break
    
elapsed_time = time.time() - start
print("elapsed_time:",elapsed_time)
print(is_prime)
格段に速くなりましたね． 試しに最初のプログラムでは日が暮れてしまう 10000000019 を入力してみても1秒かからず終わりますね． それもそのはず，10000000019**0.5 ≒ 100000 ですからこの程度コンピュータにとっては朝飯前です．

計算量について

今回，「計算量」というワードが頻繁に出てきました． これについて，解説したほうがよいでしょう．

  1. オーダー表記

    十分に大きなnに対してのざっくりとした計算量をO(・)を使って表します． オーダー表記では，一番影響力の強い項以外を無視し，定数倍の差を考慮しません．
    例えば計算量が 4*n**3 + 2*n**2 +3*n + 7 のアルゴリズムでは，十分大きなnに対しては, 4*n**3 に対して 2*n**2 +3*n + 7 は十分小さく誤差とみなすことができるため， 定数倍を無視して計算量は O(n**3) と判断できます．

  2. 最大計算量

    多くの場合に最も関心が向けられる計算量です． そのアルゴリズム(計算の方法)が最悪の場合に必要とする計算量です． 今回の素数判定の場合は O(√n) が最大計算量です

  3. 平均計算量

    そのアルゴリズムが平均してどの程度の計算を要するかを表す指標です．
アルゴリズム(計算の方法)を評価する際にはこの計算量という概念が重要になってきます． ちなみに，オーダー表記における影響力の強さ より具体的には発散の速さは1(定数) log(n) n n*log(n) n**2 2**n n!の順に大きくなっていきます． 今後の説明でちょくちょく出てくるかもしれませんが，計算量 O(log(n)) と聞いたら「結構速いんだな」くらいの認識でいてもらえれば大丈夫です． 計算量やアルゴリズムに関する参考書も挙げておきます．(C2冊とAOJの本)

素数の判定と計算量についての理解が深まったところでこんな課題を解いてみましょう．

課題

与えられた入力nに対してnまでの素数のリストを返してください．

先ほどの最速の素数判定を1からnまでのすべての数に適用すれば，すべての数に対して √n の計算が必要と考えれば， めちゃくちゃざっくり見積もって最悪でも O(n*√n) の計算で終わるはずです．(厳密に計算してみても実際にO(n*√n)になります) 実際にやってみましょう．

解法①


import time

n = int(input())

num_list = [True for i in range(n+1)]
num_list[0] = False
num_list[1] = False

start = time.time()

for num in range(n+1):
    for i in range(2,int(num**0.5)+1):
        if num%i == 0:
            num_list[num] = False
            break

elapsed_time = time.time() - start
print("elapsed_time:",elapsed_time)

prime_list = []
for i in range(n+1):
    if num_list[i]:
        prime_list.append(i)
        
print(prime_list)
O(n**1.5)なので結構時間がかかります． ここで登場するのがエラトステネスの篩という有名アルゴリズムです． 長さn+1のリストを作りインデックスが素数ならTrueとなるようにします.
以下のような手順で素数のリストを得ることができます．
  1. リストの要素をすべてTrueにしすべての数が素数であると仮定します．
  2. 0,1をFalseにします.
  3. 2の倍数をすべてFalseにします．
  4. 一番先頭のTrueの要素の倍数をFalseにします
これを素数判定のときと同じ理由で int(√n) まで繰り返せば，nまでの素数のリストを得ることができます．

解法②


n = int(input())

num_list = [True for i in range(n+1)]
num_list[0] = False
num_list[1] = False

for i in range(2,int(n**0.5)+1):
    if num_list[i] == True:
        p = i
        for j in range(p*p,n+1,p):
            num_list[j] = False
           
        prime_list = []
        for i in range(n+1):
            if num_list[i]:
                prime_list.append(i)
                
        print(p,prime_list)
   
print(prime_list)
アルゴリズムの挙動が分かりやすいように書いたコードです． 試しに100を入力してみます．
エラトステネスの篩

2の倍数 3の倍数 5の倍数 7の倍数と順番に取り除かれて行っているのが分かりますね． 証明は省きますが，このアルゴリズムはO(n*log(log(n))) の計算量で済むため元のO(n**1.5)と比べると非常に優秀です． 気になる方は「エラトステネスの篩 計算量」とでも検索していただければ計算量の証明を見つけられるかと思います．

今回は素数判定をテーマに遊んでみました． 計算量に気を付けて処理時間はできるだけ短く済ませられると嬉しいですね． 次回は素因数分解をして遊んでいこうと思います．

【目次に戻る】 次へ進む ->