メビウス関数

メビウス関数の定義は、

(1) μ(1) = 1
(2) μ(n) = 0 (n が平方因子を持つ(平方数で割り切れる)とき)
(3) μ(n) = (-1)**k (n が相異なる k 個の素因数に分解されるとき)
     n が相異なる偶数個の素数の積ならば μ(n) = 1
     n が相異なる奇数個の素数の積ならば μ(n) = -1
     **は累乗を表す。

となります。参照 Wikipedia(メビウス関数)

素数を求めるときと同様に、配列を使い求めています。

まず、配列を 1 で初期化。
それから、
2,4,6,8,10...
3,6,9,12,15...
5,15,20,25,30...
...
の位置の要素に、-1を掛けていきます。これで、

  n が相異なる偶数個の素数の積ならば μ(n) = 1
  n が相異なる奇数個の素数の積ならば μ(n) = -1

の部分を求めます。
さらに、
4,8,12,16,20...
9,18,27,36... 
25,50,75...
...
の要素(素数の2乗で割りきれる数)には、0を代入して、
  n が平方因子を持つ(平方数で割り切れる)ときμ(n) = 0
を求めます。

2以上の数で、上記どれにも該当しなかいのはあり得ないので、配列のすべてにメビウス関数の値が設定されることになります。

数字を列挙するのはなく、整数 n を与えると、メビウス関数の値が戻ってくるような形にしました。

のようにして値を得ます。


なお、範囲チェックはやってません。