[Python] 1,000,000番目の素数を求める

素数を見つけろ!

前回PHPを使ったのでそれをPythonでやろうという企画です。

PythonもPHPと同じくインタプリタ型の言語なので重い処理には不向きのはずですが果たしてどのくらい高速化できるのか…

全ての数を全ての数で割るコード(56.566s)

import time
N = 10000

if __name__ == '__main__':
    etime = time.time()
    p = 1
    i = 3

    while p < N:
        flg = True
        for k in range(2, i):
            if i % k == 0:
                flg = False
                break
        if flg == True:
            p += 1
        if p == N:
            print(round(time.time() - etime, 3),
                  i, " is ", p, " th prime number")
        i += 2

PHPと比べても4倍は遅い、さすがPython先輩裏切らないパフォーマンスです。

平方根までで除算する(0.168s)

import time
N = 10000

if __name__ == '__main__':
    etime = time.time()
    p = 1
    i = 3

    while p < N:
        flg = True
        for k in range(3, int(i**0.5)+1, 2):
            if i % k == 0:
                flg = False
                break
        if flg == True:
            p += 1
        if p == N:
            print(round(time.time() - etime, 3),
                  i, " is ", p, " th prime number")
        i += 2

平方根をsqrt()と書く方法もありますが、このように累乗の形で書くこともできます。

ちなみに数学ライブラリmathをインポートしてmath.sqrt()と書くこともできますがPHPのときと同じくパフォーマンスが悪化しました。

ただ100,000だと逆転したりでここのところは環境に依るのかも?そもそもあんまり差がない可能性がありますが。

平方を利用(0.572s)

import time

N = 10000

if __name__ == '__main__':
    etime = time.time()
    p = 1
    i = 3

    while p < N:
        flg = True
        k = 3
        while k*k <= i:
            if i % k == 0:
                flg = False
                break
            k += 2
        if flg == True:
            p += 1
        if p == N:
            print(round(time.time() - etime, 3),
                  i, " is ", p, " th prime number")
        i += 2

平方を利用したら逆に遅くなりました!!!

素数リストを使え!

素数リストで除算(0.154s)

import time
N = 10000

if __name__ == '__main__':
    etime = time.time()
    prime = [2]
    p = 1
    i = 3

    while p < N:
        flg = True
        for k in prime:
            if k*k > i:
                prime.append(i)
                break
            if i % k == 0:
                flg = False
                break
        if flg == True:
            p += 1
        if p == N:
            print(round(time.time() - etime, 3),
                  i, " is ", p, " th prime number")
        i += 2

伝家の宝刀である素数リストですが、まだまだ遅いです。

配列操作を速くできないかなと思ったんですが、標準のリストが最も速いみたいです…

ここまでの結果

10,000100,0001,000,000
None56.566s
math.sqrt()0.173s5.369s
i**0.50.168s5.823s
k*k0.572s10.581s
素数リスト0.154s3.489s

うーん、遅すぎてとても100万番目を計算しようという気になりませんね…

pypyってやつが速いぞ!!

インストールにはpyenvっていうやつが必要らしい!めんどくさいぞ!!

$ cd
$ git clone https://github.com/yyuu/pyenv.git ~/.pyenv
$ echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
$ echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
$ echo 'eval "$(pyenv init -)"' >> ~/.bash_profile
$ source .bash_profile

ここまでやったら動作する環境かどうか試してみましょう。

$ pyenv --version
pyenv 1.2.11-12-g2350e57b

こんな感じで表示されたら成功してます。

pypyのインストール

$ pyenv install --list

なんかいっぱいでてきますが、とりあえず最新っぽいやつをインストールします。

$ pyenv install pypy3.6-7.1.1
$ pyenv global pypy3.6-7.1.1
$ pyenv versions
  system
* pypy3.6-7.1.1 (set by /home/ubuntu/.pyenv/version)

これでsystemに変えてpypyが利用されるようになっていたら環境構築が終わりました。

// Before
$ python prime.py

// After
$ pypy prime.py

あとはコードはそのまま、実行するときにpythonの代わりにpypyと入力するだけです。

こんなんで変わるわけないやろ?そう思っていた時期もありました。

pypyの結果

10,000100,0001,000,000
None7.891s
math.sqrt()0.04s0.993s
i**0.50.038s0.825s155.941s
k*k0.034s0.829s26.742s
素数リスト0.033s0.483s12.221s

死ぬほど速くなっててワロタwwwwwwwwwwwwwwww

ワロタ…

相変わらずmath.sqrt()は遅い。どこで使えばいいんだ、これ?

numpy使えばもっと速いんじゃね?

と思ったのだが、pypy + numpyはなんだか環境構築が上手くいかない。

以下のコマンドを打ってみたのだがやっぱりできない、うーん?

$ pypy -m ensurepip
$ pypy -m pip install -U pip
$ pypy -m pip install numpy

誰か教えてください。

次回、C++での速度比較チャレンジやります。