2009年01月12日

ナノピコ教室:メビウス関数(1)

  

『ナノピコ教室』に掲載されている第1問目を解いてみました。

第1問目は
「メビウス関数μ(n) 1<=n<=100の値を求めよ(nは整数)」
という問題です。メビウス関数とは、

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

とのこと。
Wikipediaによれば、「数論や組合せ論における重要な関数である」とありますがが、よくわからないので、興味にある方は、Wikipediaを参照してください。
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E9%96%A2%E6%95%B0

さて、どんな役に立つのか僕にはわからないメビウス関数ですが、とりあえず、どうやって解くかを考えてみます。
まずは、素数を求めなくてはいけません。素数といえば「エラトステネスのふるい」ですね。

 static IEnumerable<int> Primes(int maxnum) {
     bool[] primes = new bool[maxnum+1];
     for (int i = 0; i <= maxnum; i++)
         primes[i] = true;
     primes[1] = false;
     int squareroot = (int)Math.Sqrt(maxnum);
     for (int i = 2; i < 11; i++) {
         if (primes[i]) {
             for (int n = i * 2; n <= maxnum; n += i)
                 primes[n] = false;
         }
     }
     for (int i = 1; i <= maxnum; i++) {
         if (primes[i] == true)
             yield return i;
     }
 }

配列の0番目の要素は処理の都合上使っていません。

Primes(100)

として呼び出せば、1から100までの素数を列挙してくれます。

なんか、思ったよりも冗長ですね。
もっと簡潔にならないかなと考えました。
・prime配列のtrue, falseを反対にすれば、最初の初期化は不要になる。
・boolではなく。intにする。
の2つの案が思い浮かびました。

2つめの案を採用した結果、以下のようなコードになりました。
一部、LINQを使っています。

 static IEnumerable<int> Primes(int maxnum) {
     int[] primes = Enumerable.Range(0, maxnum+1).ToArray();
     primes[1] = -1;  // -1 : 素数ではない
     int squareroot = (int)Math.Sqrt(maxnum);
     for (int i = 2; i <= squareroot; i++) {
         if (primes[i] > 0)
             for (int n = i * 2; n <= maxnum; n += i)
                 primes[n] = -1;
     }
     return primes.Where(n => n > 0);
 }

速度的には不利かもしれませんが、これで若干すっきりしました。
本当は、Primeクラスを作りたいところですが、このままとします。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellが独自にC#で解いたものです。



 

この記事へのトラックバックURL