C#で素因数分解してみる

13943 ワード
数学 C# LINQ .NET .NETFramework C# テキストリンク

SQLで素数求める方法ってありますよね。定義をそのまま書き下すだけの。
じゃあLinq使って同じような書き方できるんじゃないか？、というとこから走り出します。

素数を求める

まずは素数の定義からいきましょう。

Wikipediaより

素数（そすう、英: prime number）とは、1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

これをそのままLinqで書き下します。

CountPrime1
IEnumerable<int> CountPrime(int min = 0, int max = int.MaxValue)
{
    return Enumerable.Range(2, max - 1)
        .Where(s1 => Enumerable.Range(1, s1 - 2)
            .All(s2 => s1 == s2 || s1 % s2 != 0))
        .SkipWhile(s => s < min);
}

このままだと数が大きくなると列挙に時間がかかりすぎるので、ちょっと小細工します。
ある合成数の1を除く約数の最小値がxの時、その数字はx^2以上になります。
つまり、特定の数字Nが素数であるかどうかを考える時に、√N以下に約数がなければNは素数となります。
というわけでこうなります。

CountPrime2
IEnumerable<int> CountPrime(int min = 0, int max = int.MaxValue)
{
    return Enumerable.Range(2, max - 1)
        .Where(s1 => Enumerable.Range(2, (int)Math.Sqrt(s1))
            .All(s2 => s1 == s2 || s1 % s2 != 0))
        .SkipWhile(s => s < min);
}

素因数分解する

素数の求め方は既にわかっているので、まずは素直にいきましょう。
1は素因数分解できないので最初にはねてます。本当は例外投げるべきかも。

Factoring1
IEnumerable<int> Factoring(int number)
{
    if (number == 1)
        yield break;
    // 素数の一覧を取得
    var primes = CountPrime(0, number);
    var tmp = number;
    foreach (var prime in primes)
    {
        // 剰余が発生するまで割り続けて、終わったら次の素数に
        while (tmp % prime == 0)
        {

            tmp = tmp / prime;
            yield return prime;
        }
    }
}

実行するとわかりますが、これ、桁数が大きくなると素因数分解の難易度にかかわらずどんどん遅くなります。
最初に素数を全て取得している上、割り切れたかどうかに関わらず素数を全てループしているのが原因です。
というわけで逐次素数を生成していきましょう。

Factoring2
IEnumerable<int> Factoring(int number)
{
    if (number == 1)
        yield break;
    // 最小の素数をリストに
    var primes = new List<long>() { 2 };
    var tmp = number;
    // 割れなくなったらやめる
    while (tmp != 1)
    {
        foreach (var prime in primes)
        {
            // 剰余が発生するまで割り続けて、終わったら次の素数に
            while (tmp % prime == 0)
            {
                tmp = tmp / prime;
                yield return prime;
            }
        }
        if (tmp == 1)
            // 割れなくなったらやめる
            yield break;
        var maxPrime = primes.Max();
        if (Math.Sqrt(tmp) < maxPrime)
        {
            // 最大の素数が残っている数の平方より大きいなら残っている数は素数
            primes.Add(tmp);
            continue;
        }
        // 次の素数を求める
        primes.Add(Enumerable.Range(maxPrime, tmp - maxPrime)
            .First(s1 => !primes.Any(s2 => s1 % s2 == 0)));
    }
}

まだ最適化の余地は残っているとは思いますが、intの範囲内なら半秒もせずに算出してくれるので、許容範囲内かと。

ちなみに

こんなのとか

IEnumerable<long> LongRange(long startNum, long count)
{
    for (var i = startNum; i < startNum + count; i++)
        yield return i;
}

こんなの

IEnumerable<BigInteger> BigRange(BigInteger startNum, BigInteger count)
{
    for (var i = startNum; i < startNum + count; i++)
        yield return i;
}

を作ってEnumerable.Range()とかデータ型を置き換えてやれば、intの範囲外でもばっちこいです。
※BigIntegerの場合はMath.Sqrt()に対応する関数が無いので、素数の自乗と残っている数値を比較してやる必要があります

Spring抽象bean abstract=true宣言
『SSOシリーズ3』CASクラスタ配備時session異常