150421

Project Euler


Problem 512(1)

φ(n)を出力するコードを書いてみた。
（ちなみに、nが大きすぎるとエラーが出るので、

Problem 512はこの方法では解けないだろう。

私は違う方法でProblem 512を解いた。）

オンライン整数列大辞典の
A000010（http://oeis.org/A000010/list）
と比較し、答え合わせしてみる。

n = 69
phi_ary = [0]
(1..n).each{|i| phi_ary << i}
(2..n).each{|p|
  if phi_ary[p] == p
    p.step(n, p){|d| phi_ary[d] -= phi_ary[d] / p}
  end
}
phi_ary = phi_ary[1..n]

# OEIS A000010のデータ
ary0 =
[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,
 10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,
 24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,
 40,24,36,28,58,16,60,30,36,32,48,20,66,32,44]
# 一致の確認
p phi_ary == ary0