プロジェクトオイラー
http://projecteuler.net/
Q243.
分母をdとする0より大きく1より小さい分数のうち、既約のものの割合をR(d)で表す。R(d) < 15499 / 94744を満たす最も小さいdを求めよ。
これはやさしい。
dはなるべく多くの素数を使ったほうが、R(d)が小さくなるから、2から順に素数をかけていけばよい。そこでp/q = 1/2*2/3*4/5*...が問題の分数より小さくなったら、p*k/(q*k-1)が問題の分数より小さくなる最も小さいkを求めればよい。
from itertools import count
from fractions import Fractiondef is_prime(n):
for d in count(2):
if d * d > n:
return True
if n % d == 0:
return Falsedef gen_primes(m = 1):
for n in count(m + 1):
if is_prime(n):
yield nF = Fraction(15499, 94744)
f = Fraction(1)
d = 1
for p in gen_primes():
f *= Fraction(p - 1, p)
d *= p
if f < F:
break
n = int(f * d)
for k in count(1):
if Fraction(n * k, d * k - 1) < F:
break
print k * d
