Effizientesten Code für die ersten 10000 Primzahlen?

stimmen
49

Ich möchte die ersten 10000 Primzahlen drucken. Kann mir jemand dafür die effizienteste Code geben? Präzisierungen:

  1. Dabei spielt es keine Rolle, ob Ihr Code für n> 10000 ineffizient ist.
  2. Die Größe des Codes keine Rolle spielt.
  3. Sie können nicht nur schwer, die Werte in irgendeiner Art und Weise codieren.
Veröffentlicht am 03/08/2008 um 06:45
quelle vom benutzer
In anderen Sprachen...                            


28 antworten

stimmen
41

Das Sieb des Atkin ist wahrscheinlich das, was Sie suchen, dessen obere Grenze Laufzeit ist O (N / log log N).

Wenn Sie nur die Zahlen 1 mehr und 1 weniger als das Vielfachen von 6 laufen, könnte es sogar noch schneller sein, da alle Primzahlen über 3 sind 1 von einem Vielfachen von sechs entfernt. Ressource für meine Aussage

Beantwortet am 03/08/2008 um 07:03
quelle vom benutzer

stimmen
35

Ich empfehle ein Sieb, entweder das Sieb des Eratosthenes oder das Sieb des Atkin.

Das Sieb oder Eratosthenes ist wahrscheinlich die intuitive Methode von einer Liste von Primzahlen zu finden. Grundsätzlich Sie:

  1. Notieren Sie sich eine Liste von Zahlen von 2 zu, was Grenze Sie wollen, lassen Sie uns sagen, 1000.
  2. Nehmen Sie die erste Zahl, die nicht abgehakt ist (für die erste Iteration ist dies 2) und überqueren alle Vielfachen dieser Zahl aus der Liste aus.
  3. Wiederholen Sie Schritt 2, bis Sie das Ende der Liste erreichen. Alle Zahlen, die nicht abgehakt sind Primzahlen sind.

Offensichtlich gibt es eine ganze Reihe von Optimierungen, die getan werden können diesen Algorithmus schneller zu machen, aber das ist die Grundidee.

Das Sieb des Atkin verwendet einen ähnlichen Ansatz, aber leider weiß ich nicht genug über sie, es Ihnen zu erklären. Aber ich weiß, dass der Algorithmus I 8 Sekunden verknüpft nimmt die Primzahlen alle bis herauszufinden 1000000000 auf einem alten Pentium II-350

Sieb des Eratosthenes Source Code: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Sieb des Atkin Source Code: http://cr.yp.to/primegen.html

Beantwortet am 06/08/2008 um 00:49
quelle vom benutzer

stimmen
17

Dies ist nicht unbedingt gegen die Hardcoding Einschränkung, kommt aber schrecklich nah. Warum nicht programmatisch diese Liste herunterladen und ausdrucken, statt?

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

Beantwortet am 31/08/2008 um 23:20
quelle vom benutzer

stimmen
11

Gatekiller , wie etwa eine Zugabe breakzu , dass ifin der foreachSchleife? Das würde auf die Dinge beschleunigen viel , denn wenn wie 6 durch 2 teilbar ist , dass Sie nicht mit 3 und 5 prüfen müssen (ich Ihre Lösung stimmen würde sowieso , wenn ich genug Ruf hatte :-) ...)

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

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}
Beantwortet am 27/08/2008 um 21:26
quelle vom benutzer

stimmen
9

In Haskell, können wir fast Wort für Wort die mathematische Definition des Sieb des Eratosthenes aufschreiben „ Primzahlen sind natürliche Zahlen über 1 ohne zusammengesetzte Zahlen, wo Verbunde durch Aufzählung der einzelnen Primes Multiples gefunden werden “:

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

primes !! 10000 ist nahezu augenblicklich.

Verweise:


Der obige Code wird, auf Quoten zu arbeiten nur leicht gezwickt primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Zeitkomplexität stark verbessert (nur um einen Log - Faktor oben optimal) , indem sie in einer baumartigen Struktur faltet, und Raum Komplexität drastisch verbessert durch mehrstufige Primzahlen 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 die Klammern für die Gruppierung verwendet werden, kann ein Funktionsaufruf durch Juxtaposition nur bezeichnet wird, (:)ist ein cons Operator für Listen, und (.)ist eine funktionelle Zusammensetzung Betreiber: (f . g) x = (\y-> f (g y)) x = f (g x)).

Beantwortet am 24/04/2012 um 17:30
quelle vom benutzer

stimmen
9

@ Matt: log (log (10000)) ist ~ 2

Vom Wikipedia - Artikel (die Sie zitiert) Sieb des Atkin :

Dieses Sieb berechnet Primzahlen bis N unter Verwendung von O(N/log log N)Operationen mit nur N 1/2 + O (1) Bit Speicher. Das ist ein wenig besser als das Sieb des Eratosthenes , die verwendet O(N) Operationen und O (N 1/2 (log log N) / log N) Speicherbits (AOL Atkin, DJ Bernstein, 2004) . Diese asymptotische rechnerische Komplexität umfassen einfache Optimierungen, wie Rad - Faktorisierung und Aufspalten der Berechnung zu kleineren Blöcken.

Angesichts asymptotisch rechnerische Komplexität 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 wenn sie umgesetzt wird schneller sein.

Achim Flammenkamp schrieb in dem Sieb des Eratosthenes :

zitiert von:

@ num1

Für größere Intervalle etwa 10 ^ 9, mit Sicherheit für jene> 10 ^ 10, das Sieb von Eratosthenes wird durch das Sieb des Atkins und Bernstein übertrifft die irreduzible binäre quadratische Formen verwendet. Siehe ihrem Papier für Hintergrundinformationen sowie Absatz 5 von W. Galway Ph.D. These.

Daher wird für 10_000Sieb des Eratosthenes kann schneller als Sieb des Atkin sein.

Um OP Antwort der Code prime_sieve.c (zitiert von num1)

Beantwortet am 06/10/2008 um 21:03
quelle vom benutzer

stimmen
7

Mit GMP, könnte man schreiben folgendes:

#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, führt sie wie folgt:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Die Berechnung 1.000.000 Primzahlen auf dem gleichen Laptop:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP ist sehr für diese Art der Sache optimiert. Es sei denn, Sie wirklich die Algorithmen verstehen wollen, indem Sie Ihr eigenes Schreiben, würden Sie darauf hingewiesen werden, libgmp unter C zu verwenden,

Beantwortet am 29/08/2008 um 08:06
quelle vom benutzer

stimmen
4

Ich habe Code auf dem gefunden angepasst Codeproject folgendes zu erstellen:

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 + " ");
    }
}

Testen auf meinem ASP.NET Server nahm die rountine etwa 1 Minute zu laufen.

Beantwortet am 05/08/2008 um 20:55
quelle vom benutzer

stimmen
4

Nicht effizient überhaupt, aber Sie können einen regulären Ausdruck für Primzahlen zu testen.

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

Diese Tests , wenn, nach einer Zeichenkette , die aus k1“ s, k ist nicht prim (dh , ob der String besteht aus einem „ 1“ oder einem beliebigen Anzahl von „ 1“ s, der als ausgedrückt werden kann n - ary - Produkt).

Beantwortet am 03/08/2008 um 19:52
quelle vom benutzer

stimmen
3

Hier ist ein Sieb des Eratosthenes, die ich in Powershell schrieb vor ein paar Tagen. Es hat einen Parameter für die Anzahl der Primzahlen zu identifizieren, 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
}
Beantwortet am 07/09/2009 um 19:52
quelle vom benutzer

stimmen
3

Sieb des Eratosthenes ist der Weg zu gehen, weil es einfach und schnell ist. 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 zu finden Primzahlen (auf Pentium Dual Core E2140 1,6 GHz, mit Single-Core)

~ 4s lim = 100000000

Beantwortet am 21/08/2008 um 00:45
quelle vom benutzer

stimmen
2

Der deque Siebalgorithmus von BenGoldberg erwähnt verdient einen genaueren Blick, nicht nur , weil es sehr elegant ist , aber auch , weil es gelegentlich in der Praxis nützlich sein kann ( im Gegensatz zu dem Sieb des Atkin, die eine rein akademische Übung ist).

Die Grundidee hinter der Deque Siebes Algorithmus ist ein kleines, Schiebe- Sieb zu verwenden, das nur groß genug ist, um zumindest eine separaten mehr für jede der aktuell ‚aktiv‘ Primfaktoren enthalten - dh diejenigen Primzahlen, dessen Quadrat nicht übersteigt, die niedrigste Zahl zur Zeit durch das sich bewegende Sieb dargestellt. Ein weiterer Unterschied zu der SoE ist, dass die deque Sieb speichert die tatsächlichen Faktoren in die Schlitze von Kompositen, nicht booleans.

Der Algorithmus erstreckt sich die Größe des Siebes Fensters nach Bedarf, was zu einer relativ gleichmäßigen Leistung über einen weiten Bereich, bis das Sieb beginnt Überschreiten die Kapazität des Cache L1 der CPU erheblich. Die letzte Primzahl, die vollständig paßt, ist 25.237.523 (die 1,579,791st prime), die für den angemessenen Arbeitsbereich des Algorithmus eine grobe grobe Schätzung gibt.

Der Algorithmus ist ziemlich einfach und robust, und es hat sogar die Leistung über einen viel größeren Bereich als ein unsegmented Sieb des Eratosthenes. Letzteres ist viel schneller, so lange seine Siebes vollständig in den Cache paßt, dh bis auf 2 ^ 16 für eine Odds-nur mit byte-sized bools Sieb gegeben. Dann seine Leistung sinkt mehr und mehr, obwohl es immer deutlich schneller als der deque trotz der Behinderung (zumindest in kompilierten Sprachen wie C / C ++, Pascal oder Java / C #) bleibt.

Hier ist eine Wiedergabe des deque Siebalgorithmus in C #, weil ich diese Sprache zu finden - trotz vieler Mängel - viel praktischer für die Prototyping - Algorithmen und Experimente als die höchst umständlich und pedantisch C ++. (Nebenbei bemerkt: Ich bin die freie Verwendung LINQPad die es ermöglicht , direkt zu tauchen, ohne all die Unsauberkeit bei der Einrichtung von Projekten, Makefiles, Verzeichnissen oder Dingsbums, und es gibt mir den gleichen Grad an Interaktivität als Python - Prompt).

C # keinen expliziten deque Typ, aber die Ebene List<int>funktioniert gut genug für den Algorithmus zu demonstrieren.

Hinweis: Diese Version verwendet keine deque für die Primzahlen, weil es einfach keinen Sinn macht sqrt (n) aus n Primzahlen abspringt. Was gut wäre es 100 Primzahlen zu entfernen und 9900 zu verlassen? Wenigstens diese Weise alle Primzahlen sind in einem ordentlichen Vektor, bereit für die weitere Verarbeitung gesammelt.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Hier sind die beiden Hilfsfunktionen:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

Wahrscheinlich der einfachste Weg , um den Algorithmus zu verstehen , ist es als ein besonderes segmentierten Sieb des Eratosthenes , mich vorzustellen , mit einer Segmentgröße von 1, begleitet von einem Überlaufbereich , in dem die Primzahlen zur Ruhe kommen , wenn sie über das Ende des Segments schießen. Abgesehen davon, dass die einzelne Zelle des Segments (aka sieve[0]) bereits gesiebt worden , wenn wir es bekommen, weil es wurde überfahren , während es Teil des Bereichs Überlauf war.

Die Zahl , die dargestellt wird durch sieve[0]in gehalten sieve_base, obwohl sieve_frontoder window_basewäre auch ein guter Name, die Parallelen zu Bens Code oder Implementierungen ziehen segmentierter / Fenstersieb ermöglichen.

Wenn sieve[0]ein Nicht-Null - Wert enthält , dann ist dieser Wert ein Faktor sieve_base, der somit als Verbund erkannt werden kann. Da 0 - Zelle ein Vielfaches dieser Faktor ist , ist es leicht , seine nächsten Hop zu berechnen, die einfach 0 und dieser Faktor ist. Sollte diese Zelle bereits durch einen anderen Faktor belegt werden dann fügen wir einfach den Faktor wieder, und so weiter , bis wir ein Vielfaches des Faktors finden , wo kein anderer Faktor zur Zeit geparkt wird (Verlängerung des Sieb falls erforderlich). Dies bedeutet auch , dass es keine Notwendigkeit gibt , die aktuellen Arbeits Versätze der verschiedenen Primzahlen von einem Segment zum andere , wie in einem normalen segmentierten Siebes zum Speichern. Jedes Mal , wenn wir einen Faktor finden sieve[0], seine aktuellen Offset - Funktion ist 0.

Die aktuelle prime ins Spiel kommt in der folgenden Weise. Ein herausragendes kann nur werden Strom nach seinem eigenen Auftreten im Strom (dh , wenn er als besten erkannt wurde, weil nicht mit einem Faktor markiert), und es wird bis genau in dem Moment aktuell bleiben , die sieve[0]ihren Platz erreicht. Alle Untervielfachen dieser prime muss aufgrund der Aktivitäten von kleineren Primzahlen gestrichen wurden, genau wie in einem normalen SoE. Aber keiner der kleineren Primzahlen kann den Platz abschlagen, da der einzige Faktor des Platzes das Haupt selbst ist , und es ist noch nicht an diesem Punkt im Umlauf. Das erklärt die Aktionen durch den Algorithmus im Fall genommen sieve_base == current_prime_squared(was impliziert sieve[0] == 0, übrigens).

Nun der Fall sieve[0] == 0 && sieve_base < current_prime_squaredist leicht zu erklären: Es bedeutet , dass sieve_basenicht ein Vielfaches von einem der Primzahlen kleiner als die aktuelle Primzahl sein kann, sonst würde es als Verbund markiert wurden. Ich kann nicht ein höheres Vielfaches der aktuellen Primzahl entweder, da sein Wert kleiner als der Platz der aktuellen Primzahl. Daher muss es ein neues Primzahl sein.

Der Algorithmus wird offensichtlich durch das Sieb des Eratosthenes inspiriert, aber ebenso offensichtlich ist es ganz anders aus. Das Sieb des Eratosthenes leitet seine überlegene Geschwindigkeit von der Einfachheit seiner elementaren Operationen: eine einzige Indexaddition und einen Speicher für jeden Schritt der Operation alle ist, dass es für lange Zeit der Fall ist.

Hier ist ein einfaches, nicht segmentierten Sieb des Eratosthenes , die ich normalerweise für die Siebung Faktor Primzahlen im Bereich ushort verwenden, dh bis zu 2 ^ 16. Für diesen Beitrag habe ich es geändert durch Substitution über 2 ^ 16 arbeiten intfürushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

Wenn die erste Siebanlage 10000 Primzahlen eine typische L1-Cache von 32 KiByte überschritten werden, aber die Funktion ist immer noch sehr schnell (Bruchteil einer Millisekunde, auch in C #).

Wenn Sie diesen Code auf das deque Sieb vergleichen, dann ist es leicht zu sehen, dass die Operationen des deque Sieb viel komplizierter sind, und es kann nicht effektiv seine Kopf amortisieren, weil es immer die kürzest mögliche Strecke von Kreuzungen-off hat in einer Reihe (genau ein einziger Durchgang-off, nachdem alle Multiples Skipping, das bereits abgehakt worden war).

Hinweis: Der C # -Code verwendet intstatt , uintweil neuere Compiler haben eine Gewohnheit für minderwertigen Code zu generieren uint, wahrscheinlich, um die Menschen in Richtung unterzeichneten ganze Zahlen zu drücken ... In der C ++ Version des Codes oben habe ich unsignedüberall, natürlich; die Benchmark hatte in C ++ sein , weil ich es basiert auf einem vermeintlich ausreichend deque Typ wollte ( std::deque<unsigned>; es gab keinen Leistungsgewinn verwenden unsigned short). Hier sind die Zahlen für meinen Haswell Laptop (VC ++ 2015 / x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Hinweis: Die C # Zeiten sind ziemlich genau den C ++ verdoppeln Timings, die für C # und es zeigt ziemlich gut ist , die List<int>nicht lumpen, auch wenn als deque missbraucht.

Die einfache Siebes Code bläst noch das Deque aus dem Wasser, auch wenn es bereits über seine normale Arbeitsbereich (L1-Cache-Größe überschritten um 50%, mit den damit verbundenen Cache-Thrashing) arbeitet. Der dominierende Teil ist hier die aus den gesiebten Primzahlen zu lesen, und dies ist nicht viel von dem Cache-Problem nicht betroffen. In jedem Fall wurde die Funktion zum Sieben, die Faktoren von Faktoren ab, dh die Ebene 0 in einer 3-stufigen Siebes Hierarchie entwickelt, und in der Regel hat es nur ein paar hundert Faktoren oder eine geringe Anzahl von Tausenden zurückzukehren. Daher seine Einfachheit.

Leistung kann um mehr als eine Größenordnung verbessert werden , indem eine segmentierte Siebes verwendet und die Codeoptimierungs zum Extrahieren der gesiebten Primzahlen (Stufen mod 3 und zweimal ausgerollt oder Mod 15 und abgerollt einmal) und noch mehr Leistung quetscht werden könnte aus der Code durch ein mod 16 oder 30 mod Rad mit allen Zutaten (dh volles Abrollen für alle Reste) verwendet wird . So etwas ist in meiner Antwort auf erklärt finden prime positionierter Primzahl über auf Code Review, wo ein ähnliches Problem diskutiert wurde. Aber es ist schwer , den Punkt bei der Verbesserung der Sub-Millisekunden - Zeiten für eine einmalige Aufgabe zu sehen ...

Um die Dinge ein wenig zu relativieren, hier ist die C ++ Timings zum Sieben bis zu 100.000.000:

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

Im Gegensatz dazu ein segmentierter Sieb in C # mit einem paar Schnickschnack macht die gleiche Arbeit in 95 ms (keine C ++ Timings zur Verfügung, da ich Code tue Herausforderungen nur in C # im Moment).

Dinge können in einer interpretierten Sprache wie Python entschieden anders aussehen, wo jeder Betrieb hohe Kosten hat und der Dolmetscher Kopf Zwerge alle Unterschiede aufgrund vs. falsch vorhergesagten Verzweigungen oder Unterzyklus ops vorhergesagt (Verschiebung, Addition) vs. Multi-Cycle-ops (Multiplikation und vielleicht sogar Division). Das ist verpflichtet, die Einfachheit Vorteil des Sieb des Eratosthenes erodieren, und dies die deque Lösung etwas attraktiver machen könnte.

Außerdem sind viele der Timings berichtet von anderen Befragten in diesem Thema wahrscheinlich dominiert Ausgabezeit . Das ist ein ganz anderer Krieg, wo meine Hauptwaffe eine einfache Klasse ist wie folgt:

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

Das dauert weniger als 1 ms für 10000 (sortiert) Zahlen zu schreiben. Es ist eine statische Klasse, weil es für Text Inklusion bei der Codierung Herausforderung Einreichungen, mit einem Minimum an Aufwand und ohne Overhead gedacht.

Im Allgemeinen fand ich es sein , viel schneller , wenn konzentriertes Arbeiten auf ganze Chargen durchgeführt wird, Sieb mit einem gewissen Bereich bedeutet, dann extrahieren Sie alle Primzahlen in einen Vektor / Array, dann das gesamte Array sprengt, dann den nächsten Bereich Sieb und so weiter, statt alles zusammen mischt. Getrennte Funktionen haben , auch auf bestimmte Aufgaben konzentrieren macht es leichter zu mischen und anzupassen, ermöglicht es die Wiederverwendung, und es erleichtert Entwicklung / Prüfung.

Beantwortet am 19/04/2016 um 17:07
quelle vom benutzer

stimmen
2

in Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Beantwortet am 22/02/2010 um 08:45
quelle vom benutzer

stimmen
2

Das Sieb scheint die falsche Antwort zu sein. Das Sieb gibt Ihnen die Primzahlen bis zu einer Anzahl N , nicht die ersten N Primzahlen. Run @Imran oder @ Andrew Szeto, und Sie erhalten die Primzahlen bis N.

Das Sieb könnte noch brauchbar sein, wenn man Siebe immer wieder versuchen, für immer größere Zahlen, bis Sie eine bestimmte Größe Ihrer Ergebnismenge getroffen, und einige Caching von Zahlen verwenden bereits erhalten, aber ich glaube, es ist noch nicht schneller wäre als eine Lösung, wie @ Pats .

Beantwortet am 19/06/2009 um 19:12
quelle vom benutzer

stimmen
2

Anpassung und im Anschluss an Gatekiller , hier ist die letzte Version , die ich benutzt habe.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

Es ist im Grunde das gleiche, aber ich habe den „brechen auf Sqrt“ Vorschlag aufgenommen und um einige der Variablen geändert, um es für mich passen besser zu machen. (Ich war auf Euler arbeiten und brauchte das 10001th prime)

Beantwortet am 16/02/2009 um 06:17
quelle vom benutzer

stimmen
1

Mit Sieb des Eratosthenes, Berechnung durchaus vergleichen schneller „bekannt weiten“ Primzahlen-Algorithmus.

Durch die Verwendung von Pseudo - Code von ihrem Wiki (ist https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), ich in der Lage sein , die Lösung auf C # haben.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000) nimmt 2s und 330 ms.

HINWEIS : Wert könnte auf Hardware - Spezifikationen variieren abhängig.

Beantwortet am 12/05/2016 um 03:40
quelle vom benutzer

stimmen
1

Hier ist eine C ++ Lösung, eine Form von SOE mit:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Beachten Sie, dass diese Version des Sieve auf unbestimmte Zeit Primzahlen berechnen kann.

Beachten Sie auch, die STL dequenimmt O(1)Zeit durchzuführen push_back,pop_front und mit wahlfreiem Zugriff obwohl Subskribierung.

Die resizeOperation dauert O(n)Zeit, won sich die Anzahl von Elementen hinzugefügt wird. Wegen , wie wir diese Funktion verwenden, können wir behandeln diese eine kleine Konstante ist.

Der Körper der whileSchleife my_insertausgeführt O(log log n)Zeiten, in denen ndie Variable entspricht maybe_prime. Dies ist , weil die Bedingung Ausdruck der whilezu true ausgewertet wird einmal für jeden Primfaktor maybe_prime. Siehe " Divisor - Funktion “ auf Wikipedia.

Multipliziert mit der Anzahl der Male my_insertaufgerufen wird, zeigt , dass es dauern sollte O(n log log n)Zeit zur Liste nPrimzahlen ... das ist wenig überraschend, die die Zeitkomplexität das Sieb des Eratosthenes haben sollen.

Doch während dieser Code ist effizient, es ist nicht das effizienteste ... Ich würde dringend empfehlen eine Fachbibliothek für Primzahlen Generation verwenden, wie primesieve . Jede wirklich effizient, gut optimierte Lösung, mehr Code eingenommen hat , als jemand will in Stackoverflow geben.

Beantwortet am 16/04/2016 um 18:33
quelle vom benutzer

stimmen
1

Der folgende Mathcad Code die ersten Millionen Primzahlen in weniger als 3 Minuten berechnet.

Beachten Sie, dass diese Gleitkomma wäre mit verdoppelt für alle Zahlen und ist grundsätzlich interpretiert. Ich hoffe, dass die Syntax klar.

Geben Sie hier image description

Beantwortet am 02/03/2014 um 02:15
quelle vom benutzer

stimmen
1

Hier ist mein VB 2008-Code, der alle Primzahlen <10.000.000 in 1 min 27 sec auf meiner Arbeit Laptop findet. Es springt auch Zahlen und sucht nur nach Primzahlen, die <die sqrt der Prüfnummer sind. Es ist nur zu finden Primzahlen von 0 auf einen Wert sentinal gestaltet.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Beantwortet am 11/03/2011 um 03:25
quelle vom benutzer

stimmen
0

Da Sie nur die ersten 10000 Primzahlen wollen, anstatt komplexe Algorithmus Codierung werde ich folgendes vorschlagen

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

Jetzt Anruf ist prime wie Sie es brauchen

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Beantwortet am 16/11/2018 um 05:34
quelle vom benutzer

stimmen
0

Ich kann Ihnen ein paar Tipps geben, haben Sie es zu implementieren.

  1. Für jede Zahl, die Hälfte davon bekommen. Beispiel 21 überprüft, so erhält nur den Rest von ihm aus Bereich 2-10 dividiert wird.
  2. Wenn es eine ungerade Zahl ist, nur durch divide ungerade Zahl ist, und umgekehrt. Wie für 21, teilt mit 3, 5, 7, 9 nur.

Effizienteste Methode bekam ich so weit nach oben.

Beantwortet am 29/07/2018 um 19:25
quelle vom benutzer

stimmen
0

Mit Hilfe der Array.prototype.find () -Methode in Javascript. 2214.486 ms

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start   < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count  
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i  
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms
Beantwortet am 09/06/2018 um 21:49
quelle vom benutzer

stimmen
0

Hier ist der Code, den ich gemacht:


enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}
Beantwortet am 20/01/2018 um 15:50
quelle vom benutzer

stimmen
0

Hier ist mein Code, der auf meinem Laptop, erste Million Primzahlen in unter 6 Sekunden , und ersten 2.000.000 in 15 Sekunden erste 10.000 Primzahlen in 0,049655 Sekunden findet
eine kleine Erklärung. Diese Methode verwendet zwei Techniken Primzahl zu finden

  1. zunächst einmal alle nicht-Primzahl ist eine Zusammensetzung von Vielfachen von Primzahlen so Dieser Code Test die Testnummer durch kleinere Primzahlen anstelle von einer beliebigen Anzahl von Unterteilen, diese Berechnung nimmt um atleast 10mal für eine 4-stellige Zahl und noch mehr für eine größere Anzahl
  2. Zweitens außer durch prime Dividieren, es nur durch Primzahlen teilt, die an der Wurzel der Zahl, die kleiner oder gleich sind ferner getestet wird stark die Berechnungen zu reduzieren, das funktioniert, da jede Zahl, die größer als Wurzel der Anzahl ist, wird ein Gegenstück-Nummer haben, die muss kleiner sein als Wurzel der Zahl, aber da wir alle Zahlen kleiner als die Wurzel bereits getestet haben, deshalb müssen wir nicht mit der Nummer größer als die Wurzel aus der Anzahl getestet stören.

Beispielausgabe für den ersten 10.000 Primzahl
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Hier ist der Code in der Sprache C, 1 eingeben und dann 10.000 bis die ersten 10.000 Primzahlen ausdrucken.
Edit: Ich habe vergessen , diese enthalten Mathematik - Bibliothek, wenn Sie auf Windows oder Visual Studio sind als das sollte in Ordnung sein , aber unter Linux müssen Sie den Code mit -Im Argumente kompilieren oder der Code kann nicht funktionieren
Beispiel: gcc -Wall -o „% e " "% f" -Im

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}
Beantwortet am 06/05/2017 um 11:48
quelle vom benutzer

stimmen
0

Ich habe seit etwa einem Jahr auf Fund Primzahlen gearbeitet. Dies ist, was ich fand die schnellsten sein:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 Nanosekunden bis 2147483629 ab 2 zu erhalten.

Beantwortet am 14/08/2016 um 00:20
quelle vom benutzer

stimmen
0

Ich verbringe einige Zeit ein Programm schreiben , viele Primzahlen berechnen und dies ist der Code , den ich gewohnt bin mit den ersten 1.000.000.000 Primzahlen eine Textdatei zu berechnen. Es ist in Deutsch, aber der interessante Teil ist die Methode calcPrimes(). Die Primzahlen sind , in einem Array genannt Primzahlen gespeichert. Ich empfehle einen 64 - Bit - CPU , da die Berechnungen mit 64 - Bit - Integer sind.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}
Beantwortet am 23/04/2012 um 20:46
quelle vom benutzer

stimmen
0

Ich habe diese mit Python geschrieben, wie ich es gerade angefangen zu lernen, und es funktioniert völlig in Ordnung. Die 10.000ste prime durch diesen Code erzeugt das gleiche wie in der genannten http://primes.utm.edu/lists/small/10000.txt . Um zu überprüfen , ob eine nPrimzahl ist oder nicht, dividieren ndurch die Zahlen aus 2zu sqrt(n). Wenn eines dieser Bereich der Anzahl perfekt teilt , ndann ist es nicht prim.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Beantwortet am 27/12/2010 um 18:37
quelle vom benutzer

stimmen
-1
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}
Beantwortet am 08/05/2012 um 05:15
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more