Proceduren für Primzahlen

[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+

[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 ...

[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+

[Little John]

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

[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+

[ts-soft]

@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

[Little John]

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:

Code: Alles auswählen

ZufallsPrimZahl(8, 10)

Und Dein SiebDesEratosthenes() kann noch vereinfacht werden.

Gruß, Little John

[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.

[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

[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