Project Euler Problem 243

• Problem 243 - Project Euler

ある数dを分母としたとき，分子がd以下のそれ以上約分できない分数の個数をR(d)とする．
このときR(d)/d < 15499/94744となる最小のdを求める．
たとえばd = 12ならR(d)は4個(1/12, 5/12, 7/12, 11/12)．

オイラーのトーティエント関数で互いに素な個数を求めるのをエラトステネスの篩風にやって分母 - 1で割る．
以上を愚直にやったら1,2時間かかったので，いくつか素数を選んで試しに数を作って見る方法の方がいいかも．

N = 1000000001
phi = range(2, N)
for i in xrange(2, N):
    if phi[i - 2] == i:
        for j in xrange(i - 2, len(phi), i):
            phi[j] = phi[j] * float(i - 1) / i

for i in xrange(2, N):
    if phi[i - 2] / (i - 1) < 15499.0/94744:
        print i