Sehr schneller Primzahl-Finder

[negaH]

@Phantom1:

Zitat:

Primes.IndexOf(500Mio, False); ergab eine Zeit von 798ms

Delphi-Quellcode:

  while Primes[i] < 500000000 do 
    Inc(I);

ergab eine Zeit von 2869ms

Gut. Probiere nun mal folgendes aus:

Delphi-Quellcode:

  J := Primes.IndexOf(500000000);
  I := Primes.IndexOf(400000000);

  StartCounter;
  while I < J do
  begin
    Primes[I];
    Inc(I);
  end;
  StopCounter;

Mache also eine Ausschnittsberechnung.

Der obige Unterschied ist erklärbar weil die Erzeugung der Bitarrays[] getrennt von der realen Berechnung der Primzahlen abläuft. Man muß sich nun die Frage gefallen lassen: "für was benötigt man nun alle Primzahlen kleiner 2^32?"

Für die Kryptrographie sind diese Primzahlen viel zu klein.
Für die mathematische Statistik/Zahlentheorie benötigt man nur die Information wieviele Primzahlen in einem Bereich existieren, also CountOfPrimes(Start, Stop).
Um eine beliebige Zahl < 2^32 auf Primzahl zu testen findet man in meinem Source ein viel schnelleres Verfahren.

Es gibt also im Grunde eigentlich keine richtig nützliche Anwendung für die vollständig berechneten Primzahlen. Das Sieb ansich ist wohl am sinnvollsten für die Zahlentheorie, aber dort benötigt man eben nicht die reale Primzahl sondern nur die Anzahl der Primzahlen innerhalb gewisser Bereiche.


Gruß Hagen