Python（基本的なこと003: 素数定理_time, math, matplotlibライブラリ）

■ライブラリを試してみる。
今回からいくつかライブラリを試してみる。まず、PyCharmの右下のInterpreter Settingsから必要なライブラリを入れないといけない。初期の状態だと下のようになってた。すでにpipとsetuptoolsというものが入っている。右側の＋から必要なものを検索して追加する。

機械学習で必要となりそうなpandas, numpyとグラフ描画ができるmatplotlibを入れたところで下のようになった。それぞれのライブラリで必要なものも一緒にダウンロードされているよう。これでライブラリを使用する準備はできた。

いろいろと試してみて、今回使ったのは結局math, time, matplotlibの3つ。mathやtimeは標準で使えるよう。
サンプルコードは、前回の素数を探すものから少し変えて、xまでに出てくる素数の総数とその近似値になるというx/log(x)（素数定理）に値を入れてグラフにしてみた。コードは下の通り。

import math
import time
import matplotlib.pyplot as mp

# START_NUM: start number, TRY_COUNT：numbers to be checked from start number
START_NUM = 2
TRY_COUNT = 1000000
primeNumArray = [2]
primeNumSize = [1]
primeNumSize_calc = [1]

start_time = time.time()
for var in range(START_NUM, START_NUM + TRY_COUNT):
    num = var
    flag = 1
    for var2 in primeNumArray:
        result = num % var2
        if result == 0:
            flag = 0
            break
    if flag == 1:
        primeNumArray.append(var)
        primeNumSize_calc.append(var/math.log(var))
        primeNumSize.append(len(primeNumArray))

mp.plot(primeNumArray, primeNumSize, color="blue")
mp.plot(primeNumArray, primeNumSize_calc, color="red")

end_time = time.time()
print("process_time:", len(primeNumArray), ":", end_time - start_time)
mp.grid()
mp.show()

コードの説明のメモ。
2つ目のfor文（for var2 in primeNumArray:）について、すべての値に対して割り切れるか試すより今まで出てきた素数に対して割り切れるか試した方が計算量が少なくなるので、素数のリスト（primeNumArray）を割る数とした。割ることができる数がない場合は、その値を素数とみなしてリストに入れる。その際に、x/log(x)（素数の数の近似値）と実際の素数の数もそれぞれリストに入れる。

確認が終わったら、次の式でグラフにする。プロットのx軸は素数の値、y軸は実際の素数の数（青線）と素数の数の近似値（赤線）。それぞれ同じサイズのリスト。
　mp.plot(primeNumArray, primeNumSize, color="blue")
　mp.plot(primeNumArray, primeNumSize_calc, color="red")

素数の確認にかかった実行時間を得るために、timeライブラリでfor文の始めと終わりで時間をはかり差をとっている。


1000000（10^6）で実行した結果は、素数の数：78498、実行時間：292.4秒だった。実際の素数の数（青線）と素数の数の近似値（赤線）は下のグラフの通り。

上のグラフでは、数が大きくなるにつれ値が近くなるか分かりづらいので、実際の素数の数を近似値で割ったグラフも出した（下のグラフ）。数が大きくなるにつれて1に近づく傾向にある。10^6の結果では1から離れているけど、素数定理のwikiには10^25までの結果がのっており、10^25では1.018となるらしい。

もう少しライブラリを試してみる。