素数を求める

　1000までの素数を求めてみましょう。　プログラムの行数は少ないですが、新しいコマンドを使っています。for 文が２重になっていて、その中に if 文 があるところが、わかりにくいかもしれません。

 [Python例１]

sosu = [2]

n = 100001

for i in range(3,n):
    for j in range(2,i):
        if i % j == 0:
            break
    else:
        sosu.append(i)
print(sosu)

中身を説明しましょう。

　sosu というリストに、初めに素数 2 をセットしています。そして、次の素数を sosu.append(i) で加えています。

　外側の for （最初のfor）は、iを3から 1000まで変えながら、iまでの数 j で割って、余りが 0 なら素数でないとして、 breakを実行して、内側の forによる繰返しを終了します。この場合、else 文は実行されません。

break は、for の繰返しを途中で中止するコマンドです。

　また、elseは、内側のfor に対する else で、pythonに独特なものです。else の中身 sosu.append(i) は、内側の for がbreakを一度もせずに完了した時だけ（これが素数の時）、実行されます。

　このプログラムには効率の悪いところがあります。どうすれば、速く計算できるか考えてください。

次のように、いろいろなところに print文 を入れて、プログラムがどのように動いているか観察しましょう。

#1は、x (3から9の数字)をプリントします。

#2は、xを2からxまでの数字で割った数（商）と余り（剰余）をプリントしています。

#3は、余りが0だとプリントされます。

#4は、2からxまで、余りがゼロでない時にプリントされます。

#5は、プログラムの最後に一度だけプリントされます。

次のプログラムを実行してみてください。さて、どこに改善点があるでしょうか？

 [Python例2]

print("x ÷ b =")
for x in range(3,10):
    print("---<", x, "は、素数？ >---")                          #1
    for b in range(2, x):
        print(x, "÷", b, "=", int(x/b), "余り", x%b)          #2
        if x % b == 0:
            print(x, "は素数ではありません。")         #3
            break
    else:
        print(x, "は素数です。")                                  #4
print("---< おしまい >---")                                         #5

　最初のPython例では、変数 i が素数かどうかを、3~４行目で 2からi-1の数で割り切れるかで判断しています。(i - 2) 回調べることになります。i が7の場合だと 2, 3, 4, 5, 6の5回調べます。

　しかし、4以上の数で調べる必要はありません。4で割った時の商は4以下ですので、4について調べる前にチェック済みということになります。プログラムでいうと　j *j  が i 以下の数についてだけ調べれば十分です。

　また、割り算で調べる数は素数だけで十分です。

　この二点を考慮して、10万までの素数をもとめるには、次のようなプログラムになります。

[python例 3]

import time

t1 = time.time()

n = 100001

sosu = [2]

for i in range(3,n):

    for p in sosu:

        if i % p == 0:

            break

        elif p*p > i:

            sosu.append(i)

            break

    else:

        print("ここを通ることはありませんが、念のため!")

t2 = time.time()

print("素数の数は", len(sosu), n, "までで一番大きい素数", sosu[-1])

print("計算にかかった時間は", t2-t1, "秒")

　計算時間を図るために、time モジュールで、計算終了の時刻ー計算開始の時刻を表示しています。100倍以上速いでしょう。

　timeモジュールについては、モジュールの項目でも取り上げています。