dを固定して考えましょう。例えば10とか。nで取りうるのは1〜9です。しかし、nとdは互いに素なので、結局とりうるのは
1 3 7 9
の4つです。これはφ(10)です。定義そのものですね。したがって、
φ(2) + φ(3) + ... + φ(1000000)
を計算すればよいです。
φ(n)をエラトステネスのふるい的に求めましょう。基本的には素因数分解を求めるのと同じです。10までで考えて、まず0〜10の配列を用意します。
0 1 2 3 4 5 6 7 8 9 10
2から見ていきます。配列のインデックスと要素が同じなら素数です。2が素数なので、4以降の2の倍数に2を入れます。
0 1 2 3 2 5 2 7 2 9 2
次に3が素数なので同様に3を入れていきます。
0 1 2 3 2 5 3 7 2 3 2
6のところは3を入れても入れなくてもどちらでもいいですが、入れたほうが判定が無くて速いでしょうか。
こうしておいてからφを計算します。例えばφ(6)を計算しましょう。配列のインデックス6は3です。3で割り切れなくなるまで割ります。そうすると2になります。結局3で割ったので、φ(3)φ(2)で、φ(3)は2となります。あとは再帰的にφ(2)を計算します。
再帰的ではなくてメモ化したほうが速いかもと思って書いてみたら変わらなかったです。
def div_pow(n :Int, d :Int) :Int = if(n % d != 0) n else div_pow(n / d, d) def sieve(max_n :Int) :Array[Int] = { val a = new Array[Int](max_n + 1) for(n <- 1 to max_n) a(n) = n for(p <- Iterator.from(2).takeWhile(p => p * p <= max_n) if a(p) == p; n <- Iterator.range(p, max_n + 1, p)) a(n) = p a } def phi(n :Int) :Int = if(n == 1) 1 else { val p = a(n) val m = div_pow(n, p) n / m / p * (p - 1) * phi(m) } val N = 1000000 val a = sieve(N) println (Iterator.range(2, N + 1).map(n => phi(n).toLong).sum)
