素数判定アルゴリズム

Python勉強会のまとめとして初学者の方にはフィズバズが課題として出されましたが、非初学者には素数判定アルゴリズムを実装せよ、とのお題がでました。素数判定とはその名の通り、与えられた$n$が素数か否かを判定する、というものですが、RSA暗号なんかにも応用されるらしく、計算理論においては関心を集めるそうです。

判定法は大きく分けて決定的素数判定法と確率的素数判定法があります。リュカテストなどは別だそうですが、とにかく今回はWikipediaにも載っている決定的素数判定法の一つである「試し割り」を組んでみます。

実装

任意の$n$を取り、2より小さいか、2か、2で割れるか（偶数か）、問を立てていきます。2は素数ですが、その他は素数では無いのでFalseでも返しておきます。

ここまでで2まではチェックしたので、以降は$n$が3以上の場合を見ます。といっても3から$n$の1/3の値までをiでforを回して、もし$n$を割り切れるiがあればFalseを返します。偶数でないことは確かなので2ずつincrementします。奇数に2を足しても奇数ですものね。

そしてもしforループの最後までFalseが返らなければ、もうそれは素数として良いよ…ということでTrueを返します。結構ザックリですが、割と精密ですね。

def isPrime(n):
    # 0,1は素数ではない。
    if (n < 2):
        return False
    # 2は素数である。
    elif (n == 2):
        return True
    # 偶数は素数ではない。
    if (n % 2 == 0):
        return False
    # 3を始点として、入力された数値の1/3までをforで回す。
    for i in range(3,int(n/3)):
        # もしそのiで割り切れるなら素数ではない。
        if (n % i == 0):
            return False
        # ニずつincrementする。
        i+=2
    # ここまで辿りついた君は素数だ。
    return True

# 試しに走らせてみる
isPrime(5)

# もともとの10000までの素数を出力せよ、というお題への解答
for i in range(10000):
    if isPrime(i):
        print(i)

終わりに

今日は院を修了した先輩がPythonの勉強会を開いてくださりました。実際には影で奮闘してくれた先輩や同期のおかげなのですが、教室いっぱいに人が埋まって賑やかな一日でした。

色々と話し足りない感がとめどないですが、GitやPythonがゼミでパワーを持ってくれると構文解析も形式的に議論ができたり論文を分散管理できたりで嬉しいことになりそうだな1、と思いました(小声)。

  1. そういえば先輩もしばしば「これができると何が嬉しいかというと…」のような言い回しをされていたのですが、この話の持って行き方ってエンジニアあるあるなんですかね。 ↩