2

これが可能かどうかはわかりませんが、質問する必要があります。私の数学的およびアルゴリズムのスキルは、ここで私を失敗させているようなものです:P

問題は、特定の制限まで素数を生成するこのクラスがあることです。

public class Atkin : IEnumerable<ulong>
{
    private readonly List<ulong> primes;
    private readonly ulong limit;

    public Atkin(ulong limit)
    {
        this.limit = limit;
        primes = new List<ulong>();
    }

    private void FindPrimes()
    {
        var isPrime = new bool[limit + 1];
        var sqrt = Math.Sqrt(limit);

        for (ulong x = 1; x <= sqrt; x++)
            for (ulong y = 1; y <= sqrt; y++)
            {
                var n = 4*x*x + y*y;
                if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                    isPrime[n] ^= true;

                n = 3*x*x + y*y;
                if (n <= limit && n % 12 == 7)
                    isPrime[n] ^= true;

                n = 3*x*x - y*y;
                if (x > y && n <= limit && n % 12 == 11)
                    isPrime[n] ^= true;
            }

        for (ulong n = 5; n <= sqrt; n++)
            if (isPrime[n])
            {
                var s = n * n;
                for (ulong k = s; k <= limit; k += s)
                    isPrime[k] = false;
            }

        primes.Add(2);
        primes.Add(3);
        for (ulong n = 5; n <= limit; n++)
            if (isPrime[n])
                primes.Add(n);
    }


    public IEnumerator<ulong> GetEnumerator()
    {
        if (!primes.Any())
            FindPrimes();

        foreach (var p in primes)
            yield return p;
    }


    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

今、私が望むのは、シーケンスが（理論的に）決して停止しないように制限を取り除くことです。

私はそれが次のようになると考えています：

  1. 些細な制限から始める
    • 極限までのすべての素数を見つける
    • 新たに見つかったすべての素数を生成する
    • 制限を増やす (古い制限を 2 倍または 2 乗するなどして)
    • ステップ 2 に進む

そして、最適には、そのステップ 2 は古い制限と新しい制限の間でのみ機能する必要があります。言い換えれば、最低の素数を何度も見つける必要はありません。

これを行う方法はありますか？x私の主な問題は、yたとえばこのアルゴリズムの内容がよくわからないことです。同様に、同じ種類のアルゴリズムを使用して、xandyをoldLimit(最初は 1) に設定し、それを まで実行できnewLimitますか? または、それはどのように機能しますか？これに光を当てる明るい心はありますか？

これのポイントは、その制限を設定する必要がないようにすることです。たとえばTake()、制限が十分に高いかどうかなどを気にせずに、Linq と必要な数の素数を使用できるようにします。

4

4 に答える 4

3
于 2013-12-13T05:25:55.050 に答える
1

x と y が何をするのかを説明しようとすることはできますが、ループを最初からやり直さないと、あなたが求めることはできないと思います。これは、どの「ふるい」アルゴリズムでもほとんど同じです。

ふるいが行うことは、基本的に、解として各数値を持つ異なる二次方程式 (偶数または奇数) の数を数えることです。各数値に対してチェックされる特定の方程式は、n % 12 が何であるかによって異なります。

たとえば、mod 12 の余りが 1 または 5 であるnは、4* x ^2+ y ^2= nの解の数が奇数で、その数に平方がない場合にのみ、素数です。最初のループは、これらの異なる方程式を満たす可能性のあるxとyのすべての可能な値を単純にループします。そのnの解を見つけるたびに isPrime[ n ] を反転することで、解の数が奇数か偶数かを追跡できます。

問題は、これを可能なすべてのn に対して同時にカウントすることです。これにより、一度に 1 つずつチェックするよりもはるかに効率的になります。一部のnに対してのみ実行すると、時間がかかり (最初のループで n >= lower_limit であることを確認する必要があるため)、2 番目のループが複雑になります。

2 番目のループは、数値が平方フリー (素数の平方である因数を持たない) であることを確認します。

また、アトキンのふるいの実装が、エラトステネスの単純なふるいよりも必ずしも高速であるとは思いません。ただし、可能な限り高速で最適化された Atkin のふるいは、可能な限り高速で最適化された Eratosthenes のふるいを打ち負かします。

于 2009-10-14T23:20:47.237 に答える