Primzahlen-Berechnung

[Jonathan]

Abt. Primel-Gefriemel
-----------------------

Von 22 Sekunden auf 16 Sekunden... Wer hätte das gedacht . Hier die neue Version:

$P-
'PrimTurbo
'
'Turbo-Primzahlensuchprogramm

Declare Primeln#, PrimIndex&, MaxPrimel&, ActPrimel&, StartZeit&, PrimCount&, Ausgabe%, JN$, EndZeit&
Cls
Print "Primzahlen finden bis: ";
Input MaxPrimel&
UserMessages 16
Dim Primeln#, MaxPrimel& + 1
Print ""
Print "Primzahlen werden gesucht..."
StartZeit& = &gettickcount
WhileLoop 4, MaxPrimel&, 2
  Byte Primeln#, &loop = 1
EndWhile
WhileLoop 3, sqrt(MaxPrimel&) + 1, 2
  IfNot @Byte(Primeln#, &loop)
    WhileLoop &loop * &loop, MaxPrimel&, &loop << 1
      Byte Primeln#, &loop = 1
    EndWhile
  EndIf
EndWhile
EndZeit& = &gettickcount
Print ""
Print "Suchen abgeschlossen."
Print "Benötigte Zeit: " + @Str$((EndZeit& - StartZeit&) / 1000) + " Sekunden."

Print ""
Print "Primzahlen zählen (J/N)? ";
Input JN$
If @Upper$(JN$) = "J"
  Print ""
  Print "Primzahlen werden gezählt..."
  PrimCount& = 0
  WhileLoop 2, MaxPrimel&
    IfNot @Byte(Primeln#, &loop)
      Inc PrimCount&
    EndIf
  EndWhile
  Print ""
  Print "Gefundene Primzahlen: " + @Str$(PrimCount&)
EndIf
Print ""
Print "Ausgeben (0 = Nicht ausg.; 1 = Im Fenster ausgeben;"
Print "2 = In Datei ausgeben; 3 = beides)? ";
Input Ausgabe%
If (Ausgabe% Mod 2)
  Print ""
  Print "Ausgabe:"
  WhileLoop 2, MaxPrimel&
    IfNot @Byte(Primeln#, &loop)
      Print &loop
    EndIf
  EndWhile
EndIf
If (Ausgabe% \ 2)
  Print ""
  Print "Dateiausgabe..."
  Assign #1, "Primzahlen.txt"
  ReWrite #1
  WhileLoop 2, MaxPrimel&
    IfNot @Byte(Primeln#, &loop)
      Print #1, &loop
    EndIf
  EndWhile
  Close #1
EndIf
Dispose Primeln#
Print "Beliebige Taste zum Beenden drücken..."
WaitInput

Bis 10000 (1229 Primzahlen)
---------------------------
Interpreter: 0,628 Sekunden
Compiler*: 0,121 Sekunden

Bis 1M (78498 Primzahlen)
-------------------------
Interpreter: 77,491 Sekunden
Compiler: 16,356 Sekunden

Vergleichen kann ich leider nicht, da p.specht ja die anderen Male getestet hat... Würdest Du vllt. nochmal?

So, und jetzt in Assembler!!!


Gruß
Jonathan

*Juchuuu, XProfan X2 zu Weihnachten bekommen *freu*

[Jonathan]

Ach, ich sehe gerade, in diesem Thread ist ja die Assemblerversion noch gar nicht drin - hier kommt sie, mit einer Geschwindigkeit von 45 Sekunden für 1 Milliarde Primzahlen

$P-
'PrimTurbo in Assembler
'
'Eine Primzahlensuche, die abgeht wie sonstwas...
Declare Daten#, ZahlenAnzahl&, StartZeit&, JN$, PrimAnz&

'Erstellt mit dem XProfan Datengenerator, (C) Frank Abbing
'Datei: C:\Users\Jonathan\Desktop\JWASM\PrimTurbo_Hauptschleife.BIN (originale Dateigröße: 162 Bytes)
Declare Code#
Dim Code#,164
Clear Code#
Long Code#,0=1397791846,1448563281,35048,-1959228672,12977264,21022208
Long Code#,24=37799424,54576640,71353856,88131072,104908288,121685504
Long Code#,48=16827904,16859334,441,-834977536,-796187532,311087363,1946286720
Long Code#,76=-1047834384,-487075445,-1957113717,-958790696,-788332285
Long Code#,96=-210315461,29087723,-1962934272,63013832,-150736757,225955387
Long Code#,120=-1048374902,16416770,-347868555,63474671,428425679,1499094878
Long Code#,144=-1654237093,321731,-854261760,-1957165221,49920

Print "Primzahlen finden bis: ";
Input ZahlenAnzahl&
Dim Daten#, ZahlenAnzahl& + 5
Long Daten#, 0 = ZahlenAnzahl&
Long Daten#, 4 = (Sqrt(ZahlenAnzahl&) + 1) \ 1
WhileLoop 0, @SizeOf(Code#) - 4
  If @Long(Code#, &loop) = 123456789
    Long Code#, &loop = Daten#
  EndIf
EndWhile
Print "Primzahlen werden gesucht..."
StartZeit& = &gettickcount
@Call(Code#)
Print ""
Print "Fertig!"
Print "Benötigte Zeit: " + @Str$((&gettickcount - StartZeit&) / 1000) + " Sekunden."
Print "Gefundene Primzahlen: " + @Str$(@Long(Daten#, ZahlenAnzahl& + 1))

Print ""
Print "Primzahlen in Datei 'Primzahlen.txt' schreiben (J/N)? ";
Input JN$
If @Upper$(JN$) = "J"
  Print ""
  Assign #1, "Primzahlen.txt"
  ReWrite #1
  
  WhileLoop 2, ZahlenAnzahl&
    IfNot @Byte(Daten#, &loop)
      Print #1, &loop
    EndIf
    IfNot &loop Mod (ZahlenAnzahl& \ 1000)
      Locate %csrlin - 1, 1
      Print @Str$(&loop / ZahlenAnzahl& * 100) + "% geschrieben..."
    EndIf
  EndWhile
  Close #1
EndIf
Dispose Code#
Dispose Daten#
Print ""
Print "Fertig!"
WaitKey

Gruß
Jonathan

[Andreas Miethe]

Nicht schlecht !!!

1Mio Primzahlen in 0 Sekunden

[Frabbing]

Assembler halt.