(Konsolen)Programm für die Generierung von Primzahlen

redrew99

volkard schrieb:

Welches BS und wieviele Bits? Für Win32 könnte ich auf den Lagerplatten was finden.

Windows7, 64-Bit, allerdings benutze ich Code::Blocks mit einem 32-Bit Compiler.

volkard

Ich hab ne alte exe gefunden.
http://www.normannia.de/members/volkard/prime.exe
Sie zeigt an:

1 2
2 3
3 5
4 7
5 11
6 13
...
664579 9999991

Gegenprobe: http://de.wikipedia.org/wiki/Primzahlsatz
Jup, es sollten 664579 Stück sein.

volkard

Wir müssen erstmal trennen zwischen Sieben, die fortlaufende Primzahlen generieren und Tests, die keine Reihenfolge benötigen.

Bis 2^32 ist für Tests derzeit http://www.mersenneforum.org/showthread.php?p=182647 angesagt.

Für Siebe natürlich der Klassiker http://de.wikipedia.org/wiki/Sieb_von_Atkin und vermutlich für normale Bereiche stärker http://www.ieeta.pt/~tos/software/prime_sieve.html

volkard

Uups, Dein Prog ist ja auch in C++. Komisch, daß wir uns im asm-Forum getroffen haben.

redrew99

Danke!

Gleich mal ausprobiert und festgestellt, daß mein C++-Programm allein bis zur Zahl 100 000 schon 17s braucht.

redrew99

volkard schrieb:

Uups, Dein Prog ist ja auch in C++. Komisch, daß wir uns im asm-Forum getroffen haben.

Ja, ich wollte gerne mal ein Assembler- mit einem C++- Programm vergleichen.

Da aber Dein C++Programm ohnehin um so vieles schneller ist, kann ich mir den Vergleich erstmal schenken.

redrew99

volkard schrieb:

Wir müssen erstmal trennen zwischen Sieben, die fortlaufende Primzahlen generieren und Tests, die keine Reihenfolge benötigen.

Bis 2^32 ist für Tests derzeit http://www.mersenneforum.org/showthread.php?p=182647 angesagt.

Für Siebe natürlich der Klassiker http://de.wikipedia.org/wiki/Sieb_von_Atkin und vermutlich für normale Bereiche stärker http://www.ieeta.pt/~tos/software/prime_sieve.html

Ok, mein Programm zählt hoch und ermittelt anhand einer Modulorechnung, ob Primzahl ja/nein.

Wenn man siebt, dürfte sich die Geschwindigkeit um einiges erhöhen lassen.

Hatte mir das teilweise auch überlegt, also z.B. alle geraden Zahlen auszulassen, war aber mir aber nicht sicher, wie man das programmieren kann.
Werde mich aber noch mal damit beschäftigen.

volkard

redrew99 schrieb:

Da aber Dein C++Programm ohnehin um so vieles schneller ist, kann ich mir den Vergleich erstmal schenken.

Hihi.

Nachdem ich Dich jetzt ein wenig erschreckt habe, sage ich Dir, was das Programm wirklich ist:

Allein das Anzeigen so vieler Zahlen mit

#include <iostream>

using namespace std;

int main(){
    for(int i=0;i<=664579;++i)
        cout<<i<<' '<<i<<'\n';
}

dauert bei mir 46 Sekunden.

Aber ich schaff's im angegebenen Programm inclusive Primzahlenberechnung in 5 Sekunden.

Das Programm war eine Tech-Demo zur schnellen Ausgabe auf der Windows-Konsole.

volkard

redrew99 schrieb:

Hatte mir das teilweise auch überlegt, also z.B. alle geraden Zahlen auszulassen, war aber mir aber nicht sicher, wie man das programmieren kann.
Werde mich aber noch mal damit beschäftigen.

Die geraden Zahlen auszulassen ist eine gute Idee.
Das könnte zum Beispiel so aussehen, daß man statt

bool istPrim(int n)
{
   if(n<2) return false;
   for(int teiler=2;...;teiler+=1)
      if(...

dann

bool istPrim(int n)
{
   if(n<2) return false;
   if(n==2) return true;
   if(n%2==0)
      return false;
   for(int teiler=3;...;teiler+=2)
      if(...

schreibt.

redrew99

volkard schrieb:

Hihi.

...solange du mir keinen Virus ins System schmuggelst, sehe ich das recht locker

volkard schrieb:

Allein das Anzeigen so vieler Zahlen mit
#include <iostream>

using namespace std;

int main(){
    for(int i=0;i<=664579;++i)
        cout<<i<<' '<<i<<'\n';
}
dauert bei mir 46 Sekunden.

Dann ist mein Programm ja doch nicht ganz so schlecht, wie ich zuerst dachte.
(Aber immerhin rechnet es richtig, das ist doch schonmal viel Wert )

volkard schrieb:

Nachdem ich Dich jetzt ein wenig erschreckt habe, sage ich Dir, was das Programm wirklich ist:
...
Aber ich schaff's im angegebenen Programm inclusive Primzahlenberechnung in 5 Sekunden.

Das Programm war eine Tech-Demo zur schnellen Ausgabe auf der Windows-Konsole.

Wie genau funktioniert denn diese Tech-Demo? Primzahlen werden da ja vermutlich dann nicht generiert.

volkard

redrew99 schrieb:

Wie genau funktioniert denn diese Tech-Demo? Primzahlen werden da ja vermutlich dann nicht generiert.

Doch, doch. Aber mit dem Sieb des Erathostenes, das ist verflixt schnell, wenn man fortlaufende Primzahlen berechnen will.

Die Anzeige, insbesondere das Scrollen, geschieht aber in einem Offline-Speicherbereich, der nur (wenn ich mich recht erinnere) 100 mal pro Sekunde auf den Bildschirm gebracht wird, damit die lahme Windows-Konsole möglichst selten angesprochen werden muß.