読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Project Euler Problem 243

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
-->