كيف يمكنني اختبار بريماليتي؟

Question

وأنا أكتب مكتبة صغيرة مع بعض الأساليب عدد الوزراء ذات الصلة. كما فعلت الأساس (ويعرف أيضا باسم أساليب العمل)، والآن أنا أبحث عن بعض التحسين. طبعا ... الانترنت هو مكان ممتاز للقيام بذلك. لقد، ومع ذلك، عثر عليها مشكلة التقريب وكنت أتساءل كيف لحل هذه المشكلة.

في حلقة يمكنني استخدامها لاختبار عدد لانها بريماليتي انها اكثر كفاءة للبحث حتى الجذر التربيعي (ن) بدلا من ن / 2 أو حتى ن - 1. ولكن بسبب التقريب مشاكل بعض رقم حصول على تخطي وبالتالي بعض يعبي هم تخطي! على سبيل المثال، يجب أن يكون رئيس الوزراء 10000th: 104729، ولكن 'الأمثل' نسخة ينتهي مع: 103811

وبعض مدونة (انها مفتوحة لمزيد من التحسين، وأنا أعلم، ولكن لا أستطيع التعامل مع شيء واحد فقط في كل مرة):

/// <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;
}

وأنا أعلم أن جزءا التربيعية فشل لي (أنا أو تفشل)، حاول Math.Ceiling كذلك، مع حوالي نفس النتائج.

Answer 1

للأسف، لم أحاول النهج حسابي من قبل. ولكن إذا كنت ترغب في تنفيذ النهج بكفاءة، أنا أقترح القيام ببعض التخزين المؤقت. إنشاء مجموعة لتخزين كل الأعداد الأولية أقل من عتبة محددة، وملء هذه المجموعة، والبحث داخل / استخدامه.

في المثال التالي، وإيجاد ما إذا كان العدد هو رئيس الوزراء هو O (1) في أحسن الأحوال (أي عندما يكون عدد أقل من أو يساوي maxPrime، وهو 821461 لمنطقة عازلة 64K)، وهو الأمثل إلى حد ما في حالات أخرى (عن طريق التحقق من وزارة الدفاع على أرقام فقط 64K من أول 820،000 - حوالي 8٪).

و(ملاحظة: لا تأخذ هذه الإجابة مع اقتراب "الأمثل" إنها أكثر من مثال حول كيفية تحسين تنفيذ الخاص بك)

public static class PrimeChecker
{
    private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB

    private static int[] primes;
    public static int MaxPrime { get; private set; }

    public static bool IsPrime(int value)
    {
        if (value <= MaxPrime)
        {
            return Array.BinarySearch(primes, value) >= 0;
        }
        else
        {
            return IsPrime(value, primes.Length) && IsLargerPrime(value);
        }
    }

    static PrimeChecker()
    {
        primes = new int[BufferSize];
        primes[0] = 2;
        for (int i = 1, x = 3; i < primes.Length; x += 2)
        {
            if (IsPrime(x, i))
                primes[i++] = x;
        }
        MaxPrime = primes[primes.Length - 1];
    }

    private static bool IsPrime(int value, int primesLength)
    {
        for (int i = 0; i < primesLength; ++i)
        {
            if (value % primes[i] == 0)
                return false;
        }
        return true;
    }

    private static bool IsLargerPrime(int value)
    {
        int max = (int)Math.Sqrt(value);
        for (int i = MaxPrime + 2; i <= max; i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }
}

Answer 2

وأعتقد أن هذا هو مشكلتك:

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

وهذا يجب أن يكون

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

وحتى لا تحصل مربع كامل كما يعبي. أيضا، يمكنك استخدام "IDX + 2 =" بدلا من "IDX ++" لأنك لا تملك إلا أن اختبار الأعداد الفردية (كما كتب في التعليق أعلاه مباشرة ...).

Answer 3

وأنا لا أعرف إذا كان هذا هو تماما ما كنت تبحث عن ولكن إذا كنت حقا تشعر بالقلق إزاء سرعة ثم يجب أن ننظر إلى طرق probablistic لبريماليتي الاختبار بدلا من استخدام منخل. رابين ميلر هو اختبار بريماليتي احتمالي يستخدمه الرياضيات.

Answer 4

ونشرت لي فئة يستخدم غربال أو إراتوستينس لحساب الأعداد الأولية هنا:

<وأ href = "https://stackoverflow.com/questions/573692/is-the-size-of-an-array-constrained-by-the-upper-limit-of-int-2147483647/573770# 573770 "> هل حجم مجموعة مقيدة الحد الأعلى للكثافة العمليات (2147483647)؟

Answer 5

وكما قال مارك، واختبار ميلر رابين هو في الواقع وسيلة جيدة جدا للذهاب. إشارة إضافية (مع الزائفة رمز) هو مقالة ويكيبيديا عن ذلك.

وتجدر الإشارة إلى أنه في حين أنه هو احتمالي، عن طريق اختبار فقط عدد قليل جدا من الحالات، يمكنك تحديد ما إذا كان العدد هو رئيس للأرقام في كثافة (وطويلة تقريبا) مجموعة. انظر هذا الجزء من تلك المادة ويكيبيديا أو <أ href ل = "http://primes.utm.edu/prove/prove2_3.html" يختلط = "نوفولو noreferrer"> وبريماليتي إثبات مرجعية للحصول على مزيد من التفاصيل.

وأوصي أيضا قراءة هذه المقالة على الأسية وحدات، وإلا وأنت تسير أن يكون التعامل مع أعداد كبيرة جدا جدا عندما تحاول أن تفعل اختبار ميلر رابين ...

Answer 6

وقد ترغب في النظر في فيرما نظرية قليلا .

وهنا هو رمز الزائفة من كتاب الخوارزميات التي كتبها S. داسجوبتا، C.H. باباديميتريو، وU.V. Vazirani ، حيث 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 في الصدارة المذكورة كتاب . ومن كل شيء عن بريماليتي الاختبار، وربما يكون من المفيد بالنسبة لك.

Answer 7

وهذه محاولة ...

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;

وإيف استخدام هذا مرات قليلة جدا .. ليس بالسرعة غربال .. لكنه يعمل.

Answer 8

وهنا هي وظيفة لائقة في منتصف الطريق كتبت إلى حل واحدة من يولر:

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;
    }
}

Answer 9

ولدي خوارزمية سريعة لفحص الأعداد الأولية. يمكنك تحسين خوارزمية الخاص بك إذا كنت تعرف أن يعبي في شكل 6K ± 1، باستثناء 2 و 3. لذلك، أولا يمكنك اختبار إذا الإدخال القسمة على 2 أو 3. ثم تحقق من كل الأرقام من حيث الشكل 6K ± 1 ≤ √input.

bool IsPrime(int input)
        {
            //2 and 3 are primes
            if (input == 2 || input == 3)
                return true; 
            else if (input % 2 == 0 || input % 3 == 0)
                return false;     //Is divisible by 2 or 3?
            else
            {
                for (int i = 5; i * i <= input; i += 6)
                {
                    if (input % i == 0 || input % (i + 2) == 0)
                        return false;
                }
                return true;
            }
        }

Answer 10

من إراتوستينس - التي يجب أن تأخذ بها الحصول على الجذر والنقطة العائمة القضايا.

وأما بالنسبة للfloor، وسوف يكون أفضل عمل عن طريق اتخاذ ceiling.

Answer 11

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;
}

وأنا لا يمكن أن تحصل عليه أي أسرع ...

Answer 12

برايم الأرقام وبريماليتي الاختبار كانت مفيدة وخوارزمية AKS يبدو للاهتمام حتى لو كان غير عملي ولا سيما بالمقارنة مع الاختبارات القائمة على probabily.

Answer 13

وهذا يعمل بسرعة جدا ليعبي اختبار (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

Answer 14

في حالة أي شخص آخر مهتم، هنا هو بلدي التحويل الداخلي محمد لأعلى إلى VBA. وأضاف لي الاختيار لاستبعاد 1، 0، والسلبية الأرقام كما هي محددة فقط لا رئيس الوزراء.

ولقد اختبرت هذا فقط في Excel VBA:

Function IsPrime(input_num As Long) As Boolean
    Dim i As Long
    If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
        IsPrime = False: Exit Function
    ElseIf input_num = 2 Then
        IsPrime = True: Exit Function '2 is a prime
    ElseIf input_num = 3 Then
        IsPrime = True: Exit Function '3 is a prime.
    ElseIf input_num Mod 2 = 0 Then
        IsPrime = False: Exit Function 'divisible by 2, so not a prime.
    ElseIf input_num Mod 3 = 0 Then
        IsPrime = False: Exit Function 'divisible by 3, so not a prime.
    Else
        'from here on, we only need to check for factors where
        '6k ± 1 = square root of input_num:
        i = 5
        Do While i * i <= input_num
            If input_num Mod i = 0 Then
                IsPrime = False: Exit Function
            ElseIf input_num Mod (i + 2) = 0 Then
                IsPrime = False: Exit Function
            End If
            i = i + 6
        Loop
        IsPrime = True
    End If
End Function

Answer 15

ولديك لحلقة ينبغي أن تبدو هذه:

for (int idx = 3; idx * idx <= test; idx++) { ... }

وبهذه الطريقة، يمكنك تجنب الفاصلة العائمة حساب. يجب أن تعمل بشكل أسرع وأنه سوف يكون أكثر دقة. هذا هو السبب في بيان for المشروط هو مجرد تعبير منطقي: أنه يجعل مثل هذه الامور ممكن