Project Euler：Problem 7

from math import *
import time
import psyco
psyco.full()

def isprime(n, primes):
    sq = sqrt(n)
    for i in primes:
        if sq < i: break
	if n % i == 0: return False
    return True

primes = [2]
n = 10000
limit = int(n * log(n) + n * log(log(n)))
#limit = 10000000

#st = time.time()
for i in range(3,limit,2):
    if isprime(i, primes): primes.append(i)
#et = time.time()
#print et - st
print primes[n]

psycoをimportして意味もなく高速化した（いや，意味はあるけど……）．以前はRubyで以下のように書いていたが，Python使い出してからRubyの重さに絶望した．あと，isprimeとして素数判定を別の関数として行った方が速いらしい．というかTrue/Falseで判定結果返してるから速いのか？

prime = [2]
n = 10000
count = 2
# Pierre Dusart
limit = (n * Math::log(n) + n * Math::log(Math::log(n))).ceil

count_tmp = 0
3.step(limit,2) {|i|
    break if count > 10001

    prime.each {|x|
        count_tmp += 1 if i % x == 0
        break if (count_tmp > 0)||(x ** 2 > i)
    }
    if count_tmp == 0
        prime << i
        count += 1
    end
    count_tmp = 0
}

puts prime[10000]