Project Euler 0001-0010

今年末で某の一次試験が終わるとすると（終わると信じたい）、
いよいよ普段の生活で数学っぽい活動が殆ど無くなってしまうことになる。
 
このまま数学の力が落ちていってしまうのも勿体無いので、

今後は趣味として"Project Euler"をゆっくり進めていくことにする。
（いつまで興味が続くかは不明）

projecteuler.net

Project Eulerとは、一言で表せば数学クイズで競うサイトである。
特に、プログラミングを上手く用いると解ける問題が多いようである。

例えば、

Problem 10 - Project Euler

2,000,000以下の全ての素数の和を求めよ。

といった具合である。

最初の方は高校数学の範囲で解けたり、愚直に計算するだけであったりとごく簡単であるが、
番号が進むにつれてかなり難しくなっていくようである。
（statisticsから確認できる情報だと、最新の数問はいずれも世界で数百人にしか解かれていない。）

AtCoderなどの競技プログラミングとは異なり、特に時間制限などは無いため、遊びだと思ってやる気の湧いたときにゆっくり進めていこうと思う。

進捗：0001-0010 まで完了
 
問題を解く上では今の所手が止まることはなかった。

●エラトステネスの篩

N以下の素数を列挙する関数として、pythonでエラトステネスの篩を作ったのだが、動作が少し遅く感じた。

#n以下の素数
def prime_under_(n):
    num_ls = [i for i in range(2,n+1)]
    prime_ls =[]
    item = num_ls[0]
    while item < int(np.sqrt(n))+1:
        prime_ls.append(item)
        num_ls = [i for i in num_ls if i % item !=0]
        item = num_ls[0]
    return prime_ls + num_ls

%%time
prime_under_(1000000)

CPU times: user 2.4 s, sys: 159 ms, total: 2.56 s
Wall time: 2.62 s

numpyで置き換えることで、以下の通り高速化することができた。

def np_prime_under_(n):
    is_prime = np.ones(n).astype(int)
    is_prime[:2]=0
    for j in range(2,int(np.sqrt(n)+1)):
        if(is_prime[j]):
            is_prime[j*j::j] = 0
    ans_ls = np.arange(n)[is_prime]*np.array(list(range(n)))
    return list(ans_ls.nonzero()[0])

%%time
np_prime_under_(1000000)

CPU times: user 147 ms, sys: 29.8 ms, total: 176 ms
Wall time: 179 ms

また調べたところ、sympyというライブラリを使えばそのまま出せるようであった。

import sympy

%%time
ans_ls = [i for i in sympy.primerange(2, 1000000)]

CPU times: user 3.32 s, sys: 34.9 ms, total: 3.36 s
Wall time: 3.49 s

sympyを用いた場合の速度としては、numpyを使わない場合と同程度となった。

• pythonの計算で速度が求められる場合には、上手くnumpyを活用することが大事であるということを再確認できた。

• ライブラリを読み込んだとしても、numpyを使って自分で書いた方が動作が速い場合もある。