こんにちは。
私は、最近、よくProject Euler※(http://projecteuler.net/)の問題を解いています。
one-minute rule は努力目標で、問題が解けりゃいいや（＝うごけばいいや）レベルでコードを書いているので、できたコードの処理速度には目も当てられない状態になっています。。
「これではいかん」と一念発起し、処理速度向上の試みをしてみましたので、紹介します。
※プログラムで解く問題集です。
【処理速度向上対象】
今回は以下の一つのコードの高速化をすることを目的とします。
今回の処理速度向上の対象は、Project Euler 第10問(http://projecteuler.net/index.php?section=problems&id=10)に対する解答コードとしました。python2.4で書いています。
メインは素数判定部分(is_prime())の高速化です。（のちに全体の高速化も行います）
【開発環境】
Intel(R) Xeon(R) CPU 5130 @ 2.00GHz
メモリ 2GB
OS CentOS 5.5 64bit
【処理課題】
200万以下の素数の和を求めよ。
ここで、素数とは、2以上その数未満の自然数で割りきれない自然数のことです。
【最初のコード】
200万以下の奇数について、Primes.is_prime()で素数かどうかを判定し、素数であればsumに加算するという方法で答えを求めます。
素数の判定方法は、「その数の平方根以下の自然数で割ってみて、どれでも割り切れなければ素数、そうでなければ素数でない」というものです。
--------コード開始--------
class Primes1:
def is_prime(self,number):
i=2
while number >= i*i:
if not number % i: return False
i+=1
return True
def pe010_01(p):
sum = 2
for n in range(3,2*(10**6),2):
if p.is_prime(n) : sum+=n
return sum
if __name__ == '__main__':
p = Primes1()
print pe010_01(p)
--------コード終わり--------
Leave a comment