LINQ で素数を求める (C#)

素数を求める .NET (C#) のプログラムを、LINQ to Objects を利用して作成します。

素数を「自分自身より小さいすべての素数で割り切れない数」と解釈すれば、次のように実装できます。
引数に求める素数の範囲の最小値と最大値を指定できる関数として作成しています。

Program.cs


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace PrimeNumbersConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var stopwatch = Stopwatch.StartNew();
            var result = GetPrimeNumbers_Alpha(1000, 1100).ToArray();
            stopwatch.Stop();

            Array.ForEach(result, Console.WriteLine);
            Console.WriteLine("{0} seconds", stopwatch.Elapsed.TotalSeconds);
        }

        static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers_Alpha = (minValue, maxValue) =>
            new[] { new List<long>() }
                .SelectMany(primes => Enumerable2.Range2(2, maxValue)
                    .Select(i => new { primes, i }))
                .Where(_ => _.primes
                    .All(p => _.i % p != 0))
                .Do(_ => _.primes.Add(_.i))
                .Select(_ => _.i)
                .SkipWhile(i => i < minValue);
    }

    public static class Enumerable2
    {
        public static IEnumerable<long> Range2(long minValue, long maxValue)
        {
            for (var i = minValue; i <= maxValue; i++)
            {
                yield return i;
            }
        }

        public static IEnumerable<TSource> Do<TSource>(this IEnumerable<TSource> source, Action<TSource> action)
        {
            if (source == null) throw new ArgumentNullException("source");
            if (action == null) throw new ArgumentNullException("action");

            foreach (var item in source)
            {
                action(item);
                yield return item;
            }
        }
    }
}


素数を小さい順にキャッシュしておくための List<long> オブジェクトを最初に用意し、
それを各イテレーションで参照できるようにしています。
また、実装を概念的にシンプルにするため、拡張メソッドを自作しています (Range2, Do メソッド)。

 

さて、これを少し工夫すると、実行速度を大きく改善できます。

  • ある数が割り切れるとき、その約数の対は、一方が平方根以下の約数、他方が平方根以上の約数となるので、
    平方根以下の素数で割り切れるかどうかだけを調べれば十分である。
  • これに伴い、maxValue の平方根以下の素数だけをキャッシュさせておけば十分である。

これらの考慮を反映させると次のようになります。


static void Main(string[] args)
{
    var stopwatch = Stopwatch.StartNew();
    var result = GetPrimeNumbers(1000000000000, 1000000001000).ToArray();
    stopwatch.Stop();

    Array.ForEach(result, Console.WriteLine);
    Console.WriteLine("{0} seconds", stopwatch.Elapsed.TotalSeconds);
}

static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers = (minValue, maxValue) =>
    new[]
    {
        new
        {
            primes = new List<long>(),
            min = Math.Max(minValue, 2),
            max = Math.Max(maxValue, 0),
            root_max = maxValue >= 0 ? (long)Math.Sqrt(maxValue) : 0,
        }
    }
        .SelectMany(_ => Enumerable2.Range2(2, Math.Min(_.root_max, _.min  1))
            .Concat(Enumerable2.Range2(_.min, _.max))
            .Select(i => new { _.primes, i, root_i = (long)Math.Sqrt(i) }))
        .Where(_ => _.primes
            .TakeWhile(p => p <= _.root_i)
            .All(p => _.i % p != 0))
        .Do(_ => _.primes.Add(_.i))
        .Select(_ => _.i)
        .SkipWhile(i => i < minValue);


 

この実装であれば、1 兆前後の素数でも、最近のタブレット PC で 1 秒以内で求められます。

実行結果

 

ちなみに、素数の定義通りに実装するのであれば、次のようなシンプルな実装で済みます。


static readonly Func<long, long, IEnumerable<long>> GetPrimeNumbers_Org = (minValue, maxValue) =>
    Enumerable2.Range2(Math.Max(minValue, 2), maxValue).Where(i =>
        Enumerable2.Range2(2, i  1).All(j => i % j != 0));


 

F# 版も書きました: F# で素数を求める

 

作成したサンプル
PrimeNumbersConsole (GitHub)

バージョン情報
.NET Framework 4.5

参照
エラトステネスの篩 – Wikipedia
F# で素数を求める

カテゴリー: .NET Framework. タグ: . 2 Comments »

コメント / トラックバック2件 to “LINQ で素数を求める (C#)”

  1. F# で素数を求める | Do Design Space Says:

    […] LINQ で素数を求める (C#) という記事を書きましたが、 その中にある GetPrimeNumbers 関数を F# […]

  2. Azure Web ジョブでバッチを実行する | Do Design Space Says:

    […] 以下、Web ジョブの開発の流れを簡単に書いておきます。 なお、今回作成したサンプルは TaskWebJob (GitHub) にあります。バッチ処理の題材として、素数を求めています。 […]


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。