Seite 1 von 1
Proceduren für Primzahlen
Verfasst: 29.11.2009 18:16
von Christian+
Ich ein paar Proceduren zum Umgang mit Primzahlen erstellt da ich glaube das diese relativ schnell sind und vielleicht ja auch mal jemand anderes diese brauchen kann veröffentliche ich diese hier mal.
Falls jemand eine noch schnellere Lösung hat kann er es gerne schreiben.
Code: Alles auswählen
Procedure.q NextPrime(number.q)
Protected max.q, divisor.q
Protected isPrime
If number < 3
ProcedureReturn 2
EndIf
number + 1 - (number % 2)
Repeat
isPrime = #True
max = IntQ(Sqr(number))+1
divisor = 3
While divisor <= max
If number % divisor = 0
isPrime = #False
Break
EndIf
divisor + 2
Wend
If isPrime = #True
ProcedureReturn number
EndIf
number + 2
ForEver
EndProcedure
Procedure.q IsPrime(number.q)
Protected max.q, divisor.q
If number < 3
If number = 2
ProcedureReturn #True
EndIf
ProcedureReturn #False
EndIf
If number%2 = 0
ProcedureReturn #False
EndIf
divisor = 3
max = IntQ(Sqr(number))+1
While divisor < max
If number%divisor = 0
ProcedureReturn #False
EndIf
divisor = divisor+2
Wend
ProcedureReturn #True
EndProcedure
Procedure.q RandomPrime(min.q, max.q)
Protected random.q
If NextPrime(min)>max
ProcedureReturn -1
EndIf
Repeat
random = Random(max-min)+min
random = NextPrime(random)
Until random < max
ProcedureReturn random
EndProcedure
Procedure SiebDesEratosthenes(Array status.b(1), max.q)
Protected j.q, i.q , wurzel.q
status(0) = 1
status(1) = 1
i = 4
While i <= max
status(i) = 1
i = i+2
Wend
i = 3
wurzel = IntQ(Sqr(max))+1
While i <= wurzel
If status(i) = 0
j = i*i
While j <= max
status(j) = 1
j = j+i+i
Wend
EndIf
i = i+2
Wend
EndProcedure
mfg Christian+
Re: Proceduren für Primzahlen
Verfasst: 29.11.2009 18:42
von STARGÅTE
Hm jo, kannst dir ja mal das Thema angucken :
Primzahlen generieren, dort wurde schon n bisschen was dazu geschrieben, vllt findest du ja dann auch verbesserungsmöglichkeiten bei dir ...
Re: Proceduren für Primzahlen
Verfasst: 29.11.2009 19:28
von Christian+
@STARGÅTE das Thema kenn ich schon werde es aber mir noch mal in Ruhe morgen anschauen vielleicht kann ich einem der Codes da noch was abschauen was meine schneller macht aber die Codes von da die ich mit meinen verglichen hatte waren langsamer.
mfg Christian+
Re: Proceduren für Primzahlen
Verfasst: 29.11.2009 20:31
von Little John
Christian+ hat geschrieben:Falls jemand eine noch schnellere Lösung hat kann er es gerne schreiben.
Du kannst ja mal den Code vernünftig einrücken. So wie er jetzt ist, habe ich jedenfalls keine Lust ihn mir näher anzusehen.
Gruß, Little John
Re: Proceduren für Primzahlen
Verfasst: 29.11.2009 21:40
von Christian+
@Little John So schlimm ist es doch nicht wie es jetzt eingerückt ist oder? Ich werde es aber noch mal versuchen der hat mir nur beim Einfügen das immer etwas durcheinander gebracht werde das jetzt noch mal testen.
Edit: Müsste jetzt etwas besser sein.
mfg Christian+
Re: Proceduren für Primzahlen
Verfasst: 29.11.2009 21:50
von ts-soft
Christian+ hat geschrieben:@Little John So schlimm ist es doch nicht wie es jetzt eingerückt ist oder?
Deine unvollständige Einrückung machte ein lesen zur Tortur
Danke das Du es geändert hast
Re: Proceduren für Primzahlen
Verfasst: 30.11.2009 01:50
von Little John
Christian+ hat geschrieben:Edit: Müsste jetzt etwas besser sein.
Du siehst sicherlich selbst den Unterschied. Und wenn Du nun noch berücksichtigst, dass wir im Gegensatz zu Dir den Code zum ersten Mal sehen ... Es hat schon seinen Grund, warum das konsequente Einrücken von Code Standard ist.
Deine erste Funktion würde ich so schreiben:
Code: Alles auswählen
EnableExplicit
Procedure.q NextPrime (n.q)
Protected max.q, divisor.q
Protected isPrime
If n < 2
ProcedureReturn 2
EndIf
n + 1 + (n % 2) ; next odd number
Repeat
isPrime = #True
max = IntQ(Sqr(n))
divisor = 3
While divisor <= max
If n % divisor = 0
isPrime = #False
Break
EndIf
divisor + 2
Wend
If isPrime = #True
ProcedureReturn n
EndIf
n + 2
ForEver
EndProcedure
;-- Demo
Debug NextPrime(7)
Debug NextPrime(456)
Dass ich englische Bezeichnungen bevorzuge ist nur eine Nebensache (weil hier manchmal auch internationale Kollegen nach Code suchen).
Da die Funktion Quads zurückgeben kann muss sie als
Procedure.q definiert sein. Die Verwendung eines Flags (#True/#False) verbessert IMHO die Lesbarkeit. Der Haupttrick ist, dass vor Beginn der Schleife die nächste ungerade Zahl > n bestimmt wird. Dadurch kann man innerhalb der Schleife die geraden Zahlen komplett vergessen, und immer gleich die nächste ungerade Zahl prüfen (n + 2).
Zu Deiner Funktion IsPrimZahl():
Code: Alles auswählen
While teiler < max
If start%teiler = 0
ProcedureReturn 0
Break
EndIf
teiler = teiler+2
Wend
Das
Break ergibt hier keinen Sinn.
Zu Deiner Funktion ZufallsPrimzahl() ... probiere beispielsweise mal folgenden Aufruf:
Und Dein SiebDesEratosthenes() kann noch vereinfacht werden.
Gruß, Little John
Re: Proceduren für Primzahlen
Verfasst: 30.11.2009 09:57
von PureLust
Hier mal eine kleine Routine, die ich mal Mitte 2006 für ein anderes Forum geschrieben hatte - war damals glaube ich so mit die performanteste.
Hier auf meinem kleinen Lappy mit schwacher ULV-CPU berechnet sie z.B. die 664.579 Primzahlen von 1 - 10.000.000 in knapp 395ms.
Code: Alles auswählen
; Primzahlen-Routine - 07.06.2006 by Luke
OpenConsole()
Print("Kleine Primzahlenberechnung.")
Start:
Print(Chr(10)+Chr(10)+Chr(10)+"Bitte gib die Zahl ein, bis zu der die Primzahlen berechnet werden sollen."+Chr(10)+"MaxZahl (2-250000000): ")
Eingabe.l = Val(Input())
If Eingabe < 2 Or Eingabe > 250000000 : End : EndIf
DisableDebugger
Dim Prim.b(Eingabe/2+1) ; <<<<<<<<<<<< Hier kann zu Speed-Testzwecken auch mal ein .w oder .l Array angelegt werden
Wurzel.l = Sqr(Eingabe)+1
Primzahlen.l = Int(Eingabe/2+0.6)
StartTimer = timeGetTime_()
!align 8
For y = 3 To Wurzel Step 2
If Not Prim(y>>1)
z = Pow(y,2)
!align 8
While z <= Eingabe
!align 8
If Not Prim(z>>1)
!align 8
Prim(z>>1) = 1
Primzahlen - 1
EndIf
!align 8
z + y+y
Wend
EndIf
Next y
StopTimer = timeGetTime_()
PrintN("Gefundene Primzahlen : "+Str(Primzahlen)+Chr(10)+"Berechnungsdauer : "+StrF((StopTimer - StartTimer)/1000,3)+" Sekunden")
; Im Array Prim() können nun wenn gewünscht die Primzahlen abgerufen werden:
If Primzahlen <= 1000 ; Ausgabe verhindern, wenn mehr als 1000 Primzahlen gefunden wurden
If Eingabe >= 2: Print("2"+Chr(9)) : EndIf
For n = 1 To (Eingabe-1)/2
If Not Prim(n)
Print(Str(n*2+1)+Chr(9))
EndIf
Next n
EndIf
EnableDebugger
Goto Start
Greetz, PL.
Re: Proceduren für Primzahlen
Verfasst: 30.11.2009 21:14
von Christian+
@PureLust scheint schnell zu sein dein Code werde ihn mir später noch genauer anschauen und mit meinem vergleichen.
@Little John das break und Procedure.q ist klar hatte ich übersehen. Die Idee mit englischen Namen ist gut werde ich in Zukunft beachten. Den Trick für die Ungeraden Zahlen habe ich übernommen macht aber von der Geschwindigkeit her gesehen so gut wie nichts aus.
mfg Christian+
Edit: @PureLust Ich habe mir jetzt deinen Code noch mal gründlich angeschaut. Was du das mit dem !align 8 machst habe ich nicht ganz kapiert. Die Idee mit dem im Array nur ungerade zahlen speichern habe ich übernommen und in meine inzwischen verbesserte Version des SiebDesEratosthenes eingebaut. (Bei mir Windows 7 64Bit scheint mein Code etwas schneller zu sein um das endgültig sagen zu können muss ich aber mal ein Test machen wenn ich meinen Code an den Aufbau deines Code angepasst habe.)
Code: Alles auswählen
Procedure SiebDesEratosthenes2(Array status.b(1), max.q)
Protected i.q, j.q, wurzel.q, anzahl.q
status(0) = 1
i = 3
wurzel = IntQ(Sqr(max))+1
anzahl = IntQ(max/2+0.6)
max = max/2+max%2
While i <= wurzel
If status(IntQ(i/2)) = 0
j = i*i/2
While j < max
If status(j) = 0
status(j) = 1
anzahl = anzahl-1
EndIf
j = j+i
Wend
EndIf
i = i+2
Wend
ProcedureReturn anzahl
EndProcedure
OpenConsole()
Print("Primzahlenberechnung.")
Start:
Print(Chr(10)+Chr(10)+"Bitte gib die Zahl ein, bis zu der die Primzahlen berechnet werden sollen."+Chr(10)+"MaxZahl (2-250000000): ")
Eingabe.l = Val(Input())
If Eingabe < 2 Or Eingabe > 250000000 : End : EndIf
StartTimer = timeGetTime_()
Dim Prim.b(Eingabe/2+Eingabe/2)
Primzahlen=SiebDesEratosthenes2(Prim(),Eingabe)
StopTimer = timeGetTime_()
PrintN("Gefundene Primzahlen : "+Str(Primzahlen)+Chr(10)+"Berechnungsdauer : "+StrF((StopTimer - StartTimer)/1000,3)+" Sekunden")
If Primzahlen <= 1000
If Eingabe >= 2: Print("2"+Chr(9)) : EndIf
For n = 1 To (Eingabe-1)/2
If Not Prim(n)
Print(Str(n*2+1)+Chr(9))
EndIf
Next n
EndIf
Goto Start
Re: Proceduren für Primzahlen
Verfasst: 30.11.2009 21:48
von Helle
PureLusts Routine ist schnell, weil die ermittelten Primzahlen nicht direkt abgespeichert werden sondern als Tag im Array vermerkt sind (ist keine Kritik
!). Kann je nach beabsichtigtem Verwendungszweck durchaus sinnvoll sein. Ich will hier aber mal eine Routine zur allgemeinen Primzahl-Ermittlung vorstellen, die meines Wissens nach im PB-Forum noch nicht gezeigt wurde: Das Summenverfahren von Gerald Bühler. Die ermittelten Primzahlen werden direkt abgespeichert und stehen sofort zur Verfügung.
Code: Alles auswählen
;Primzahl-Ermittlung nach dem Summenverfahren von Gerald Bühler (http://www.geraldbuehler.de)
;"Helle" Klaus Helbing, 30.11.2009, PB 4.40 Beta 7 (x86, x64)
;Die ermittelten Primzahlen stehen im Array Prime, angezeigt werden zum Test die ersten 1000 (wenn vorhanden)
Eingabe.i = Val(InputRequester("Primzahl-Berechnung", "Bitte Endwert eingeben:", "")) ;ohne Plausibilitäts-Prüfung!
Endwert.i = Sqr(Eingabe) + 1
Dim Prime.i(Int(Eingabe/(Log(Eingabe) - 1.1))) ;Anzahl der erwarteten Primzahlen + Reserve (Legendre, Gauß)
Dim PrimeSumme.i(Int(Sqr(Eingabe)/(Log(Sqr(Eingabe)) - 1.1))) ;Bereich analog Endwert
ATime = ElapsedMilliseconds()
Prime(0) = 2
x.i = 3
While x < Eingabe
y = 0
IsPrime = #True
While y < PrimeCounter And IsPrime And Prime(y) <= Endwert
While PrimeSumme(y) < x
PrimeSumme(y) + Prime(y)
Wend
If PrimeSumme(y) = x
IsPrime = #False
EndIf
y + 1
Wend
If IsPrime
PrimeCounter + 1
Prime(PrimeCounter) = x
EndIf
x + 1
Wend
ETime = ElapsedMilliseconds() - ATime
If PrimeCounter = > 1000
AnzeigeEnde = 1000
Else
AnzeigeEnde = PrimeCounter
EndIf
For i = 0 To AnzeigeEnde
Prime$ + Str(Prime(i)) + " "
Next
MessageRequester("Primzahl-Ermittlung (Anzeige auf max. 1000 begrenzt)", "Anzahl Primzahlen bis " + Str(Eingabe) + ": " + Str(PrimeCounter + 1) + " in " + Str(ETime) + " ms" + #CRLF$ + Prime$)
Viel Spass!
Gruß
Helle