続素数を求める - 匣の向こう側

素数であるかどうかはコーディングレベルで考えると、ある数が既に見つけられた素数で割りきれなければ素数となります。

int n = 19;
foreach (int p in primes) 
    if (n % p == 0)
        // 素数ではない
        return false;
// 素数
return true;

例を挙げるとこんな感じです。

しかし、これは処理的には単純ですが、素数を求めるという目的に比べて(ループを回して探すことは)コンピュータよりな手段だと感じます。プログラミングは解決すべき問題に近いところから、ネジや釘みたいなものを作るところまで、様々なレベルがあるので大変です。このレベルのギャップを解決出来れば、もう少しプログラミングが楽になると思います。

プログラミングをしていて良く出くわす問題の１つに、集合に対して「１つ以上の要素が条件を満たす」「全ての要素が条件を満たす」というものがあります。プログラム的にはループ回すだけで数行で書けるので放置されていましたが、思考レベルが著しく現実の問題から離れるため、プログラミングをする上で思った以上に影響があったかも知れないです。

さて、ここでLINQに話を移します。LINQの機能としては何はともかくクエリー式に目が行きますが、肝は拡張メソッドによる配列に類する(IEnumerableをサポートする)データ構造の拡張です。ただの配列もLINQにかかればこの通り。

int arr = new  { 1,2,3,4,5,6,7,8,9,0 };

if (arr.Any (x => x % 2 == 0)) 
    // 偶数を含む
if (arr.All (x => x % 2 == 0))
    // 配列は全て偶数

配列は手軽でよく使われるデータ構造なので、一段上のレベルで問題解決出来るようになる効果は大きいと思います。

LINQで解決したこと、してないこと

昨日、ネタ半分にLINQを使って素数を求めるプログラムを書きました。アレはプログラムを書く人間の都合(短く書きたい)だけを重要視して、パフォーマンスを無視してしまったので、もう少し現実の制約に目を向けたプログラムにしてみます。Listで実装し直し。

using System;
using System.Query;
using System.Collections.Generic;

static class Program {
    public static List<int> GetPrimes(int max) {
        List<int> primes = new List<int> ();
        primes.Add (2);
        for (int i = 3; i <= max; ++i)
            // 「primesに含まれる素数のどれかがiを割り切れる」ことがなければ
            if (!primes.Any (x => i % x == 0))
                primes.Add (i);
        return primes; 
    }

    public static void Main () {
        foreach (var p in GetPrimes (100))
            Console.Write ("{0},", p);
        Console.WriteLine ();
    }
}

上記の素数判断部分の「・・・ことがなければ」が人間の思考的には回りくどいですよね。「primesに含まれる素数全てがiを割り切れない」の方が人間の思考に近い気がしますので、早速修正してみます。

if (primes.All (x => i % x != 0))
    primes.Add (i);

流石LINQです。要素をループさせるところまで思考レベルを下げる必要がありません。

ところで・・・

この素数を求める処理は気づかないうちに前提条件を設けてしまっていることにお気づきでしょうか。maxまでの素数を求めているのですが、もし、maxに１以下を指定されたらどうなるでしょうか？実はこのままだとmaxの値に関わらず素数として2が含まれてしまいます。では、

if (max < 2)
    return primes;
primes.Add (2);

勿体ぶった割に簡単に解決しましたね。しかし、この解決方法にスッキリしない人もいるかも知れません。

List<int> primes = new List<int> ();
for (int i = 2; i <= max; ++i) 
    // primesに含まれる素数全てがiを割り切れない
    if (primes.All (x => i % x != 0))
        primes.Add (i);

「ループを2から回せばmaxが1以下の場合、ループが回らず、素数は0件になるし、こっちの方がエレガントだよ」

なるほど。

あ、でも、2を判定するときは、primesの要素数は０件。

    if (primes.All (x => i % x != 0))

この判定は大丈夫でしょうか？

結論は問題なしです。primesが空の場合、primes.Allはtrue、primes.Anyはfalseになります。上手くできていますね。

最後にパフォーマンスを考えたもっと現実的な解を出して終わりにします。

using System;
using System.Query;
using System.Collections.Generic;

static class Program {
    public static List<int> GetPrimes(int max) {
        List<int> primes = new List<int> ();
        if (max < 2)
            return primes;
        primes.Add (2);
        for (int i = 3; i <= max; i+=2)
            if (primes.FindAll (x => i >= x * x).All (x => i % x != 0))
                primes.Add (i);
        return primes; 
    }

    public static void Main () {
        foreach (var p in GetPrimes (1000))
            Console.Write ("{0},", p);
        Console.WriteLine ();
    }
}

短くスッキリとは行きません。

(追記) 何の説明もなく投げっぱなしなのもどーかと思ったので。
素数を探す場合、2以外の全ての偶数は対象外なので奇数のみでループを回した方が効率的です。そうなると、ループは3から始めてi+=2で回すことになり、forの開始をi=2とした修正が無意味になってしまいました。勿論、max<2に対応対応するため、入り口で引数チェックして場合分けを加えます。また、素数を調べるには数学的に平方根以下の素数で割りきれるかどうかまでで十分なのでFindAllも追加する羽目に。

っということで、パフォーマンス等の制約や条件により、低レベルな(コンピュータに近い)思考が必要になってしまいます。以上、蛇足ながら・・・

primes.FindAllでx <= √iに絞っていますが、これを入れた方が速いかどうかは確認してません。(^^;

(追記) FindAllで指定した条件が逆でした。しかも、絞った方が遅いです。FindAllを使わずにループを回せということか・・・