[解決済み] 素数を生成する最もエレガントな方法【クローズド版

質問

この機能を実装する最もエレガントな方法は何でしょう。

ArrayList generatePrimes(int n)

この関数は最初の n の素数を生成します (編集: ここで n>1 である場合）、だから generatePrimes(5) は ArrayList と {2, 3, 5, 7, 11} . (私はこれをC#でやっていますが、Javaの実装でも構いませんし、他の類似の言語でも構いません(Haskellではありません))。

私はこの関数を書く方法を知っていますが、昨晩それを実行したところ、私が期待していたほど素敵な結果にはなりませんでした。以下は、私が思いついたものです。

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

明らかに非効率であることは避けたいが、速度についてはあまり気にしていない。どの方法（ナイーブ、ふるい、その他）を使っても構いませんが、かなり短く、どのように動作するか明白であって欲しいと思っています。

編集 : 多くは私の実際の質問に答えなかったが、回答してくれたすべての人に感謝する。繰り返しになりますが、私は素数のリストを生成するコードの素敵なクリーンピースが欲しかったです。私はすでにそれを行う方法の束の異なる方法を知っているが、私はそれができるように明確でないコードを書く傾向がある。このスレッドでは、いくつかの良いオプションが提案されています。

• 私がもともと持っていたもののより良いバージョン (Peter Smit、jmservera、Rekreativc)
• エラトステネスの篩の非常に綺麗な実装 (starblue)
• Java の BigInteger と nextProbablePrime は非常にシンプルなコードで、特に効率的であるとは思えませんが (dfa)
• LINQを使用して、素数のリストを遅延して生成します(Maghis)
• たくさんの素数をテキストファイルに入れ、必要なときに読み込む(darin)

編集2 : 私は を C# で実装しました。 に実装してみました。これらはすべて、最初の n の素数を効果的に見つけることができます (そして、私は まともな方法 を使用して、ふるい分けに提供する上限を見つけることができます)。

どのように解決するのですか？

有益な回答をしてくださった方々に感謝します。以下は、私が実装した、最初の n を求めるいくつかの異なる方法をC#で実装したものです。最初の2つの方法は、ここに投稿されたものとほぼ同じです。(投稿者の名前はタイトルの横にあります。) Atkinのふるいはいつかやろうと思っていますが、現在ここにある方法ほど簡単にはいかないと思われます。もし、これらの方法のどれかを改善する方法を知っている人がいたら、ぜひ教えてほしいです。）

標準的な方法 ( ピーター・スミット , jmservera , レクレアティヴ )

最初の素数は2であり、これを素数のリストに追加する。次の素数は、このリスト上のどの数でも均等に割り切れない次の数である。

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

これは、テストする数の平方根まで割り切れるかどうかだけをテストし、奇数だけをテストすることによって最適化されています。の形の数だけをテストすることによって、さらに最適化することができます。 6k+[1, 5] または 30k+[1, 7, 11, 13, 17, 19, 23, 29] または で .

エラトステネスの篩 ( スターブルー )

に対するすべての素数を見つけます。 k . のリストを作るには、最初の n の素数のリストを作成するために、まず最初に n の値を近似する必要があります。次のような方法である。 に記述されているように で、これを行います。

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

スンダラムのふるい

私が発見したのは このふるい を発見したのは最近ですが、これは非常に簡単に実装することができます。私の実装はエラトステネスのふるいほど高速ではありませんが、素朴な方法よりはかなり高速です。

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}