هل هناك خوارزمية بسيطة يمكنها تحديد ما إذا كانت x هي الأولية ، ولا تخلط بين مجرد مبرمج مميت؟

Question

لقد كنت أحاول العمل في طريقي من خلال مشروع أولر ، ولاحظت حفنة من المشكلات تطلب منك تحديد عدد أولي كجزء منه.

1. أعلم أنه يمكنني فقط تقسيم x على 2 ، 3 ، 4 ، 5 ، ... ، جذر مربع من x ، وإذا وصلت إلى الجذر التربيعي ، فيمكنني (بأمان) أن أفترض أن الرقم أولي. لسوء الحظ ، يبدو هذا الحل تمامًا.

2. لقد بحثت في خوارزميات أفضل حول كيفية تحديد ما إذا كان الرقم مسبقًا ، لكن أشعر بالارتباك بسرعة.

هل هناك خوارزمية بسيطة يمكنها تحديد ما إذا كانت x هي الأولية ، ولا تخلط بين مجرد مبرمج مميت؟

شكرا جزيلا!

Answer 1

الخوارزمية الأولى جيدة جدًا وتستخدم كثيرًا في مشروع Euler. إذا كنت تعرف الحد الأقصى للرقم الذي تريده ، فيمكنك أيضًا البحث عن غربال Eratosthenes.

إذا كنت تحتفظ بقائمة الأعداد الأولية ، فيمكنك أيضًا تحسين أول algo لتقسيمها فقط بأعداد الأولية حتى الجذر التربيعي للرقم.

مع هاتين الخوارزتين (تقسيم والخلال) ، يجب أن تكون قادرًا على حل المشكلات.

يحرر: الاسم الثابت كما هو مذكور في التعليقات

Answer 2

لتوليد جميع الأرقام الأولية أقل من حد غربال eratosthenes (تحتوي الصفحة على المتغيرات في 20 لغة برمجة) هي الحل الأقدم والأبسط.

في بيثون:

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

مثال:

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

Answer 3

أرى أنه تم بالفعل اقتراح اختبار Fermat البدائي ، لكنني كنت أعمل من خلاله هيكل وتفسير برامج الكمبيوتر, ، ويعطون أيضا اختبار ميلر رابين (انظر القسم 1.2.6 ، المشكلة 1.28) كبديل آخر. لقد كنت أستخدمه بنجاح لمشاكل Euler.

Answer 4

إليك تحسينًا بسيطًا لطريقتك التي ليست غربال eratosthenes ولكن من السهل جدًا تنفيذها: حاول أولاً تقسيم x على 2 و 3 ، ثم حلقة على J = 1..SQRT (x)/6 ، في محاولة لتقسيمها بحلول 6*J-1 و 6*J+1. هذا يتخطى تلقائيًا على جميع الأرقام القابلة للقسمة بمقدار 2 أو 3 ، ويكسب لك تسريع عامل ثابت للغاية.

Answer 5

مع الأخذ في الاعتبار الحقائق التالية (من Mathschallenge.net):

• جميع الأعداد الأولية باستثناء 2 غريبة.
• يمكن كتابة جميع الأعداد الأولية التي تزيد عن 3 في النموذج 6K - 1 أو 6K + 1.
• لا تحتاج إلى التحقق من الجذر التربيعي لـ N.

إليك وظيفة C ++ التي أستخدمها لصغيرة نسبيًا n:

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

ربما يمكنك التفكير في المزيد من التحسينات الخاصة بك.

Answer 6

أوصي اختبار فيرمات البدائي. إنه اختبار احتمالي ، لكنه في كثير من الأحيان بشكل مدهش. وهو سريع بشكل لا يصدق بالمقارنة مع الغربال.

Answer 7

بالنسبة لأرقام صغيرة معقولة ، فإن x ٪ n لـ te to SQRT (x) سريع وسهل الترميز.

تحسينات بسيطة:

اختبار 2 والأرقام الفردية فقط.

الاختبار 2 و 3 ومضاعفات 6 + أو - 1 (جميع الأعداد الأولية بخلاف 2 أو 3 هي مضاعفات 6 +/- 1 ، لذلك أنت فقط تخطي جميع الأرقام الزوجية وجميع مضاعفات 3

اختبار الأرقام الأولية فقط (يتطلب حساب أو تخزين جميع الأعداد الأولية حتى SQRT (X))

يمكنك استخدام طريقة Sieve لإنشاء قائمة بجميع الأعداد الأولية بسرعة إلى حد تعسفي ، ولكنه يميل إلى أن تكون كثيفة الذاكرة. يمكنك استخدام مضاعفات 6 خدعة لتقليل استخدام الذاكرة إلى 1/3 من كل رقم.

لقد كتبت فئة رئيسية بسيطة (C#) تستخدم اثنين من الحقول لمضاعفات 6+1 ومضاعفات 6-1 ، ثم يقوم بإجراء بحث بسيط ... وإذا كان الرقم الذي أختبره خارج حدود الغربال ، ثم يعود إلى الاختبار بمقدار 2 و 3 ومضاعفات 6 +/- قبلة مبدأ الإضرابات مرة أخرى!

لقد كتبت فئة رئيسية تستخدم غربالًا لتحرير الأعداد الأولية الأصغر مسبقًا ، ثم تعتمد على الاختبار بمقدار 2 و 3 ومضاعفات من ستة +/- 1 لتلك خارج نطاق الغربال.

Answer 8

بالنسبة لمشروع Euler ، فإن وجود قائمة من الأعداد الأولية أمر ضروري حقًا. أود أن أقترح الحفاظ على قائمة تستخدمها لكل مشكلة.

أعتقد أن ما تبحث عنه هو غربال eratosthenes.

Answer 9

حقك هو أبطال هو أبطأ. يمكنك تحسينه إلى حد ما.

ابحث في استخدام المعامل بدلاً من الجذور المربعة. تتبع الأعداد الأولية الخاصة بك. تحتاج فقط إلى تقسيم 7 على 2 و 3 و 5 لأن 6 هو مضاعف 2 و 3 ، و 4 مضاعف 2.

ذكر RSLite إيرانثينوس غربال. إنه مستقيم إلى حد ما. لدي عدة لغات في المنزل. أضف تعليقًا إذا كنت تريد مني نشر هذا الرمز لاحقًا.

---

ها هو بلدي C ++ واحد. يحتوي على متسع كبير للتحسين ، لكنه سريع مقارنة بإصدارات اللغات الديناميكية.

// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>

int main(void) {
        // using unsigned short.
        // maximum value is around 65000
        const unsigned short max = 50000;
        unsigned short x[max];
        for(unsigned short i = 0; i < max; i++)
                x[i] = i + 2;

        for(unsigned short outer = 0; outer < max; outer++) {
                if( x[outer] == 0)
                        continue;
                unsigned short item = x[outer];
                for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
                        unsigned int searchvalue = item * multiplier;
                        unsigned int maxValue = max + 1;
                        for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
                                if(x[maxIndex] != 0) {
                                        maxValue = x[maxIndex];
                                        break;
                                }
                        }
                        for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
                                if( searchvalue > maxValue )
                                        break;
                                if( x[searchindex] == searchvalue ) {
                                        x[searchindex] = 0;
                                        break;
                                }
                        }
                }
        }
        for(unsigned short printindex = 0; printindex < max; printindex++) {
                if(x[printindex] != 0)
                        std::cout << x[printindex] << "\t";
        }
        return 0;
}

سأرمي رمز Perl و Python الذي لديّ بمجرد العثور عليه. فهي متشابهة في الأسلوب ، مجرد خطوط أقل.

Answer 10

فيما يلي اختبار بدائي بسيط في D (المريخ الرقمي):

/** 
 * to compile:
 * $ dmd -run prime_trial.d
 * to optimize:
 * $ dmd -O -inline -release prime_trial.d 
 */
module prime_trial;

import std.conv : to;  
import std.stdio : w = writeln;

/// Adapted from: http://www.devx.com/vb2themax/Tip/19051 
bool 
isprime(Integer)(in Integer number) 
{
  /* manually test 1, 2, 3 and multiples of 2 and 3 */
  if (number == 2 || number == 3)
    return true;
  else if (number < 2 || number % 2 == 0 || number % 3 == 0)
    return false;

  /* we can now avoid to consider multiples 
   * of 2 and 3. This can be done really simply 
   * by starting at 5 and incrementing by 2 and 4 
   * alternatively, that is: 
   *    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...    
   * we don't need to go higher than the square root of the number */
  for (Integer divisor = 5, increment = 2; divisor*divisor <= number; 
       divisor += increment, increment = 6 - increment) 
    if (number % divisor == 0)
      return false;

  return true;  // if we get here, the number is prime
}

/// print all prime numbers less then a given limit
void main(char[][] args) 
{
  const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
  for (uint i = 0; i < limit; ++i) 
    if (isprime(i))
      w(i);
}

Answer 11

أنا أعمل من خلال مشكلات مشروع Euler أيضًا ، وفي الواقع انتهيت للتو من رقم 3 (حسب المعرف) وهو البحث عن أعلى عامل رئيسي في الرقم المركب (الرقم في؟ هو 600851475143).

لقد نظرت إلى جميع المعلومات عن الأعداد الأولية (تقنيات الغربال التي سبق ذكرها هنا) ، وعلى عامل عدد صحيح على ويكيبيديا وتوصلت إلى خوارزمية تقسيم تجريبي القوة الغاشمة التي قررت القيام بها.

لذا ، بينما أقوم بمشاكل euler لتعلم روبي كنت أبحث في ترميز خوارزمية الخاص بي وتعثرت عبر مكتبة Mathn التي لديها أ فئة برايم و فئة عدد صحيح مع prime_division طريقة. كم ذلك رائع. تمكنت من الحصول على الإجابة الصحيحة للمشكلة في مقتطف روبي:

require "mathn.rb"
puts 600851475143.prime_division.last.first

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

Answer 12

أنا أحب رمز بيثون هذا.

def primes(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] ==  i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    return [j for j in xrange(2, limit) if x[j] == 1]

يمكن استخدام متغير من هذا لتوليد عوامل العدد.

def factors(limit) :
    limit += 1
    x = range(limit)
    for i in xrange(2,limit) :
        if x[i] == i:
            x[i] = 1
            for j in xrange(i*i, limit, i) :
                x[j] = i
    result = []
    y = limit-1
    while x[y] != 1 :
        divisor = x[y]
        result.append(divisor)
        y /= divisor
    result.append(y)
    return result

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

Answer 13

لم يتم تحسينه ولكنها وظيفة بسيطة للغاية.

    function isprime(number){

    if (number == 1)
        return false;

    var times = 0;

    for (var i = 1; i <= number; i++){
        if(number % i == 0){
            times ++;
        }
    }
        if (times > 2){
            return false;
        }

    return true;
    }

Answer 14

ربما يمكن أن يكون هذا التنفيذ في Java مفيدًا:

public class SieveOfEratosthenes {

    /**
     * Calling this method with argument 7 will return: true true false false true false true false
     * which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
     * 5 is prime, 6 is NOT prime, 7 is prime.
     * Caller may either revert the array for easier reading, count the number of primes or extract the prime values
     * by looping.
     * @param upTo Find prime numbers up to this value. Must be a positive integer.
     * @return a boolean array where index represents the integer value and value at index returns
     * if the number is NOT prime or not.
     */
    public static boolean[] isIndexNotPrime(int upTo) {
        if (upTo < 2) {
            return new boolean[0];
        }

        // 0-index array, upper limit must be upTo + 1
        final boolean[] isIndexNotPrime = new boolean[upTo + 1];

        isIndexNotPrime[0] = true; // 0 is not a prime number.
        isIndexNotPrime[1] = true; // 1 is not a prime number.

        // Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
        // Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
        // Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
        // Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
        // Repeat process until i * i > isIndexNotPrime.len.
        // Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
        // primes above 121..
        for (int i = 2; i < isIndexNotPrime.length; i++) {
            if (i * i >= isIndexNotPrime.length) {
                break;
            }
            if (isIndexNotPrime[i]) {
                continue;
            }
            int multiplier = i;
            while (i * multiplier < isIndexNotPrime.length) {
                isIndexNotPrime[i * multiplier] = true;
                multiplier++;
            }
        }

        return isIndexNotPrime;
    }

    public static void main(String[] args) {
        final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
        assert !indexNotPrime[2]; // Not (not prime)
        assert !indexNotPrime[3]; // Not (not prime)
        assert indexNotPrime[4]; // (not prime)
        assert !indexNotPrime[5]; // Not (not prime)
        assert indexNotPrime[6]; // (not prime)
        assert !indexNotPrime[7]; // Not (not prime)
    }
}

Answer 15

خوارزمية اختبار AKS Prime:

Input: Integer n > 1  


if (n is has the form ab with b > 1) then output COMPOSITE  

r := 2  
while (r < n) {  
    if (gcd(n,r) is not 1) then output COMPOSITE  
    if (r is prime greater than 2) then {  
        let q be the largest factor of r-1  
        if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break  
    }  
    r := r+1  
}  

for a = 1 to 2sqrt(r)log n {  
    if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE  
}  

output PRIME;   

Answer 16

طريقة أخرى في بيثون هي:

import math

def main():
    count = 1
    while True:
        isprime = True

        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break

        if isprime:
            print count


        count += 2


if __name__ == '__main__':
    main()