14

いくつかの素数関連のメソッドを含む小さなライブラリを作成しています。私は基礎（別名作業方法）を行ったので、今はいくつかの最適化を探しています。もちろん、インターネットはそうするのに最適な場所です。しかし、丸めの問題に遭遇し、これを解決する方法を考えていました。

数の素数をテストするために使用するループでは、n/2 または n - 1 の代わりに sqrt(n) まで検索する方が効率的です。たとえば、10000 番目の素数は 104729 のはずですが、「最適化された」バージョンは 103811 になります。

いくつかのコード (より多くの最適化のために開いていることは知っていますが、一度に 1 つのことしか処理できません):

/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
    // 0 and 1 are not prime numbers
    if (test == 0 || test == 1) return false;

    // 2 and 3 are prime numbers
    if (test == 2) return true;

    // all even numbers, save 2, are not prime
    if (test % 2 == 0) return false;

    double squared = Math.Sqrt(test);
    int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));

    // start with 5, make increments of 2, even numbers do not need to be tested
    for (int idx = 3; idx < flooredAndSquared; idx++)
    {
        if (test % idx == 0)
        {
            return false;
        }
    }
    return true;
}

2乗部分が失敗する（または失敗する）ことを知っており、Math.Ceilingも試してみましたが、ほぼ同じ結果が得られました。

4

16 に答える 16

10

これがあなたが探しているものであるかどうかはわかりませんが、速度が本当に気になる場合は、ふるいを使用するのではなく、素数性をテストするための確率論的方法を検討する必要があります。Rabin-Millerは、Mathematica で使用される確率的素数性テストです。

于 2009-03-09T19:33:19.610 に答える
10

これがあなたの問題だと思います：

for (int idx = 3; idx < flooredAndSquared; idx++)

これは

for (int idx = 3; idx <= flooredAndSquared; idx++)

したがって、平方数を素数として取得することはできません。また、「idx ++」の代わりに「idx += 2」を使用できます。これは、奇数をテストするだけでよいためです（上記のコメントに書いたように...）。

于 2009-03-09T18:32:38.960 に答える
4

マークが言ったように、ミラーラビン素検定は実際には非常に良い方法です。追加のリファレンス（擬似コード付き）は、それに関するWikipediaの記事です。

確率的ですが、ごく少数のケースをテストすることで、整数がint（およびほぼ長い）範囲の数値の素数であるかどうかを判断できることに注意してください。詳細については、そのWikipediaの記事のこの部分、または素数判定のリファレンスを参照してください。

また、べき乗剰余に関するこの記事を読むことをお勧めします。そうしないと、ミラーラビン検定を実行しようとするときに非常に大きな数を処理することになります...

于 2009-03-10T09:52:07.113 に答える
3

フェルマーの小定理を調べてみてください。

これは、 S. Dasgupta、CH Papadimitriou、および UV Vazirani による本 Algorithms の疑似コードです。n は、素数性をテストする数値です。

Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
   return yes
else
   return no

フェルマーの定理の実装は、ふるいのソリューションよりも高速である必要があります。ただし、フェルマーのテストに合格し、素数ではないカーマイケル数があります。これには回避策があります。前述の本 のセクション 1.3 を参照することをお勧めします。それはすべて素数テストに関するものであり、あなたにとって役立つかもしれません。

于 2009-03-09T21:36:09.613 に答える
1

これは、オイラーの1つを解決するために私が書いた中途半端な関数です:

private static long IsPrime(long input)
{
    if ((input % 2) == 0)
    {
        return 2;
    }
    else if ((input == 1))
    {
        return 1;
    }
    else
    {
        long threshold = (Convert.ToInt64(Math.Sqrt(input)));
        long tryDivide = 3;
        while (tryDivide < threshold)
        {
            if ((input % tryDivide) == 0)
            {
                Console.WriteLine("Found a factor: " + tryDivide);
                return tryDivide;
            }
            tryDivide += 2;
        }
        Console.WriteLine("Found a factor: " + input);
        return -1;
    }
}
于 2009-03-09T18:32:23.907 に答える
1

これを試して...

if (testVal == 2) return true;
if (testVal % 2 == 0) return false;

for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
   if (testVal % i == 0)
       return false;
}

return true;

私はこれをかなりの回数使用しました.ふるいほど速くはありません..しかし、それは機能します.

于 2009-03-09T18:33:26.667 に答える
1

何よりもまず、素数は 2 から始まります。2 と 3 は素数です。素数は 2 または 3 で割り切れないはずです。残りの素数は 6k-1 および 6k+1 の形式です。SQRT(入力)までの数値を確認する必要があることに注意してください。このアプローチは非常に効率的です。お役に立てば幸いです。

public class Prime {

    public static void main(String[] args) {
        System.out.format("%d is prime: %s.\n", 199, isPrime(199)); // Prime
        System.out.format("%d is prime: %s.\n", 198, isPrime(198)); // Not prime
        System.out.format("%d is prime: %s.\n", 104729, isPrime(104729)); // Prime
        System.out.format("%d is prime: %s.\n", 104727, isPrime(982443529)); // Prime
    }

    /**
     * Tells if a number is prime or not.
     *
     * @param input the input
     * @return If the input is prime or not
     */
    private boolean isPrime(long input) {
    if (input <= 1) return false; // Primes start from 2
    if (input <= 3) return true; // 2 and 3 are primes
    if (input % 2 == 0 || input % 3 == 0) return false; // Not prime if dividable by 2 or 3
    // The rest of the primes are in the shape of 6k-1 and 6k+1
    for (long i = 5; i <= Math.sqrt(input); i += 6) if (input % i == 0 || input % (i + 2) == 0) return false;
    return true;
    }

}
于 2015-11-14T03:36:39.130 に答える
0 
private static bool IsPrime(int number) {
    if (number <= 3)
        return true;
    if ((number & 1) == 0)
        return false;
    int x = (int)Math.Sqrt(number) + 1;
    for (int i = 3; i < x; i += 2) {
        if ((number % i) == 0)
            return false;
    }
    return true;
}

私はそれをこれ以上速く得ることができません...

于 2009-03-09T22:02:49.283 に答える
0

素数と素数性のテストは有用だと思いました。おそらくベースのテストと比較して特に実用的ではありませんが、AKS アルゴリズムは興味深いように思えます。

于 2009-11-02T10:20:05.257 に答える
0

これは、素数のテストに非常に高速に機能します（vb.net）

Dim rnd As New Random()
Const one = 1UL

    Function IsPrime(ByVal n As ULong) As Boolean
        If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
           return false
        End If

        Dim s = n - one

        While s Mod 2 = 0
            s >>= one
        End While

        For i = 0 To 10 - 1
            Dim a = CULng(rnd.NextDouble * n + 1)
            Dim temp = s
            Dim m = Numerics.BigInteger.ModPow(a, s, n)

            While temp <> n - one AndAlso m <> one AndAlso m <> n - one
                m = (m * m) Mod n
                temp = temp * 2UL
            End While

            If m <> n - one AndAlso temp Mod 2 = 0 Then
                Return False
            End If
        Next i

        Return True
    End Function
于 2015-11-10T09:49:23.753 に答える
0

エラトステネスのふるいを試してみてください。これにより、ルートと浮動小数点の問題が解決されるはずです。

についてはfloor、 を服用することでより良いサービスが提供されますceiling。

于 2009-03-09T18:29:34.850 に答える