Der effizienteste Code für die ersten 10000 Primzahlen?

  • Ich möchte die ersten 10000 Primzahlen drucken. Kann mir jemand den effizientesten Code dafür geben? Erläuterungen:

    1. Es spielt keine Rolle, ob Ihr Code für n & gt; 10000 ineffizient ist.
    2. Die Größe des Codes spielt keine Rolle.
    3. Sie können die Werte nicht einfach auf irgendeine Weise hart codieren.
    07 August 2012
    Viktor Mellgren
23 answers
  • Das Sieb von Atkin ist wahrscheinlich das, was Sie suchen, sein oberer gebundene Laufzeit ist O (N / log log N).

    Wenn Sie nur die Zahlen 1 und 1 weniger als die Vielfachen von 6 ausführen, könnte es da noch schneller sein Alle Primzahlen über 3 sind 1 von einem Vielfachen von 6 entfernt. Ressource für meine Aussage

    01 March 2013
    timrauRookie
  • Dies ist nicht strikt gegen die Hardcoding-Einschränkung, kommt aber schrecklich nahe. Warum nicht diese Liste programmatisch herunterladen und stattdessen ausdrucken?

    http://primes.utm.edu/lists/small/10000.txt

    01 September 2008
    John with waffle
  • In Haskell können wir fast mathematisch die mathematische Definition des Siebs von Eratosthenes aufschreiben. Primzahlen sind natürliche Zahlen über 1 ohne zusammengesetzte Zahlen, bei denen Composites durch Aufzählung der Primzahlen gefunden werden multiples ":

     primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                    [] primes)
     

    primes !! 10000 ist nahezu augenblicklich.

    Referenzen:


    Der obige Code lässt sich leicht so anpassen, dass er nur mit Quoten arbeitet, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) . Die Zeitkomplexität wird durch Falten in einer baumähnlichen Struktur erheblich verbessert (um einen Faktor log über dem optimalen Wert), und die Raumkomplexität ist drastisch verbessert durch Mehrstufige Primes Produktion , in

     primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
      where
        _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
        _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
        pairs    (xs:ys:t)  = union xs ys : pairs t
        sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                         | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]
     

    (In Haskell werden die Klammern zum Gruppieren verwendet. Ein Funktionsaufruf wird nur durch Nebeneinanderstellen gekennzeichnet. (:) ist ein cons -Operator für Listen. und (.) ist ein funktionaler Kompositionsoperator: (f . g) x = (\y -> f (g y)) x = f (g x) ).

    15 August 2018
    Will Ness
  • @Matt: log (log (10000)) ist ~ 2

    Aus dem Wikipedia-Artikel (den Sie zitiert haben) Sieb von Atkin :

    Dieses Sieb berechnet Primzahlen bis N Verwenden von O(N/log log N) Operationen mit nur N 1/2 + o (1) Speicherbits. Das ist etwas besser als das Sieb von Eratosthenes, das O(N) Operationen und O (N 1/2 (log log N) / log N verwendet ) Speicherbits (AOL Atkin, DJ Bernstein, 2004) . Diese asymptotischen Berechnungskomplexitäten umfassen einfache Optimierungen, wie die -Faktorierung von Rädern, und die Aufteilung der Berechnung in kleinere Blöcke.

    Angesichts asymptotischer rechnerischer Komplexitäten entlang O(N) (für Eratosthenes) und O(N/log(log(N))) (für Atkin) können wir nicht sagen (für kleine N=10_000), welcher Algorithmus, falls er implementiert wird, schneller ist.

    Achim Flammenkamp schrieb in Das Sieb der Eratosthenes :

    Zitiert von:

    @ num1

    Für Intervalle größer etwa 10 ^ 9, sicherlich für die & gt; 10 ^ 10, das Sieb des Eratosthenes wird durch das Sieb von Atkins und Bernstein übertroffen, das irreduzible binäre quadratische Formen verwendet. Hintergrundinformationen zu sowie Abschnitt 5 von W. Galways Ph.D. These.

    Daher kann das Sieat von Eratosthenes für 10_000 schneller sein als Siebe von Atkin.

    Um auf OP zu antworten, lautet der Code prime_sieve.c (zitiert von num1)

    07 October 2008
    jfs
  • Mit GMP könnte man folgendes schreiben:

     #include <stdio.h>
    #include <gmp.h>
    
    int main() {
      mpz_t prime;
      mpz_init(prime);
      mpz_set_ui(prime, 1);
      int i;
      char* num = malloc(4000);
      for(i=0; i<10000; i++) {
        mpz_nextprime(prime, prime);
        printf("%s, ", mpz_get_str(NULL,10,prime));
      }
    }
     

    Auf meinem 2,33 GHz Macbook Pro wird wie folgt ausgeführt:

     time ./a.out > /dev/null
    
    real    0m0.033s
    user    0m0.029s
    sys    0m0.003s
     

    Berechnung von 1.000.000 Primzahlen auf demselben Laptop:

     time ./a.out > /dev/null
    
    real    0m14.824s
    user    0m14.606s
    sys     0m0.086s
     

    GMP ist für diese Art der Dinge stark optimiert. Wenn Sie die Algorithmen nicht wirklich durch das Schreiben Ihrer eigenen Algorithmen verstehen möchten, sollten Sie libGMP unter C verwenden.

    29 August 2008
    hoyhoy
  • Nicht effizient, aber Sie können einen regulären Ausdruck verwenden, um Primzahlen zu testen.

     /^1?$|^(11+?)\1+$/
     

    Dies prüft, ob k für einen String, der aus k ? ??1 "s besteht, nicht prim ist (dh ob Die Zeichenfolge besteht aus einem ??1 oder einer beliebigen Anzahl von [??1 s, die als n -ary-Produkt ausgedrückt werden können.

    02 February 2010
    Konrad Rudolph
  • Ich habe den Code in CodeProject zum Erstellen angepasst Folgendes:

     ArrayList primeNumbers = new ArrayList();
    
    for(int i = 2; primeNumbers.Count < 10000; i++) {
        bool divisible = false;
    
        foreach(int number in primeNumbers) {
            if(i % number == 0) {
                divisible = true;
            }
        }
    
        if(divisible == false) {
            primeNumbers.Add(i);
            Console.Write(i + " ");
        }
    }
     

    Wenn Sie dies auf meinem ASP.NET-Server testen, dauert der Rountine-Vorgang ungefähr 1 Minute.

    07 August 2008
    GateKiller
  • Sieat of Eratosthenes ist der Weg zu gehen, weil es einfach ist Geschwindigkeit. Meine Implementierung in C

     #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <math.h>
    
    int main(void)
    {
        unsigned int lim, i, j;
    
        printf("Find primes upto: ");
        scanf("%d", &lim);
        lim += 1;
        bool *primes = calloc(lim, sizeof(bool));
    
        unsigned int sqrtlim = sqrt(lim);
        for (i = 2; i <= sqrtlim; i++)
            if (!primes[i])
                for (j = i * i; j < lim; j += i)
                    primes[j] = true;
    
        printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
        for (i = 2; i < lim; i++)
            if (!primes[i])
                printf("%d\n", i);
    
        return 0;
    }
     

    CPU Zeit zum Finden von Primzahlen (bei Pentium Dual Core E2140 1,6 GHz mit Single-Core) )

    ~ 4s für lim = 100.000.000

    21 August 2013
    Sam Martin
  • Hier ist ein Sieb von Eratosthenes, das ich vor einigen Tagen in PowerShell geschrieben habe. Es verfügt über einen Parameter zum Bestimmen der Anzahl der Primzahlen, die zurückgegeben werden sollen.

     #
    # generate a list of primes up to a specific target using a sieve of eratosthenes
    #
    function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
        param ($target,$count = 0)
        $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
        $sieve = @($false) * $sieveBound
        $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
        for ($i = 1; $i -le $crossLimit; $i ++) {
            if ($sieve[$i] -eq $false) {
                $prime = 2 * $i + 1
                write-debug "Found: $prime"
                for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                    $sieve[$x] = $true
                }
            }
        }
        $primes = @(2)
        for ($i = 1; $i -le $sieveBound; $i ++) {
            if($count -gt 0 -and $primes.length -ge $count) {
                break;
            }
            if($sieve[$i] -eq $false) {
                $prime = 2 * $i + 1
                write-debug "Output: $prime"
                $primes += $prime
            }
        }
        return $primes
    }
     
    07 September 2009
    Eric Schoonover
  • In Python

     import gmpy
    p=1
    for i in range(10000):
        p=gmpy.next_prime(p)
        print p 
     
    22 February 2010
    John La Rooy