プロジェクトオイラー
http://projecteuler.net/index.php
Q72.
分母が100万以下の0より大きく1より小さい既約分数の数
要するに、φ(n)の総和だが、φ(n)を一つずつ求めると時間がかかる。
a = [ (n, True) for n in range(N + 1) ]
とする。タプルの最初がφ(n)で2番目が素数かどうか。p=2から始めて、pの倍数なら、φ(n)を1-1/p倍し、素数をFalseにする。そうしていくと、素数判定しながらφ(n)が計算できる。実にエレガントである。コードもたったの10行。単純にφ(n)を求めるより1桁速い。ただ、大きなリストを作るのが難点。
N = 10 ** 6
a = [ (n, True) for n in range(N + 1) ]
a[1] = (0, False)
for p in xrange(2, N + 1):
if a[p][1]:
a[p] = (p - 1, True)
for q in xrange(p * 2, N + 1, p):
a[q] = (a[q][0] / p * (p - 1), False)print sum(map(lambda b: b[0], a))
