10001番目の素数

Project Euler 7

2, 3, 5, 7, 11 そして 13 が先頭から 6 つの素数であり、13 が 6 番目の素数である。
10001番目の素数は何？

---

エラトステネスの篩を用いて算出する。
素数リストを作成し、3以上の自然数（i）を順番に除算し、割り切れた場合は合成数と判定する。
なお、素数リストの $\lfloor\sqrt{i}\rfloor + 1$ まで割り切れない場合、当該自然数は素数となることに着目し、計算量を大幅に削減している。

# SAMPLE_1

from math import sqrt
N = 10001

prime_list = [2]
i = 3
while(len(prime_list) < N):
    for j in prime_list:
        if j > int(sqrt(i)) + 1:
            prime_list.append(i)
            break
        if i % j == 0:
            break
    else:
        prime_list.append(i)
    i += 2
print sorted(prime_list, reverse=True)[0]