プロジェクトオイラー
http://projecteuler.net/index.php
Q69.
n ≤ 1000000 でn/φ(n)が最大になるn
n = pn1e1pn2e2…pnmemと素因数分解されるなら、φ(n)/n = (1-1/pn1)(1-1/pn2)…(1-1/pnm)だから、n = 2 * 3 * …。
...
N = 1000000
n = 1
for p in gen_prime():
if n * p > N:
print n
break
n *= p
プロジェクトオイラー
http://projecteuler.net/index.php
Q69.
n ≤ 1000000 でn/φ(n)が最大になるn
n = pn1e1pn2e2…pnmemと素因数分解されるなら、φ(n)/n = (1-1/pn1)(1-1/pn2)…(1-1/pnm)だから、n = 2 * 3 * …。
...
N = 1000000
n = 1
for p in gen_prime():
if n * p > N:
print n
break
n *= p