PureBoard

Verfasst: **30.11.2008 17:27**

Ich suche einen schnelleren Code als folgenden um die nächste Primzahl nach einer beliebigen anderen Zahl zu ermitteln. Also, ich ruf die Funktion mit 3100 auf, und der Code gibt mir die erste Primzahl >= 3100 zurück.

Also nicht, alle Primzahlen von 0 - unendlich sondern immer eine rauspicken.

Code: Alles auswählen

Procedure _NextPrime(num.l)
  Protected prime.l, i.l, start.l
  Repeat
    x = Round(Sqr(num), 1)
    For i = 2 To x
      If num%i = 0 : prime = #False : Break
      Else : prime = #True : EndIf
    Next
    If prime = #False : num + 1
    Else
    Break : EndIf
  ForEver
  ProcedureReturn num
EndProcedure

Verfasst: **30.11.2008 17:36**

Hallo
Sieht nütlich aus

hab aber keine idee.

MfG
RR

Verfasst: **30.11.2008 17:40**

Code: Alles auswählen

Procedure _NextPrime(num.l)
  Protected prime.l, i.l, start.l
  num + 1
  Repeat
    i = 2
    While i * i < num
      If num%i = 0 : prime = #False : Break
      Else : prime = #True : EndIf
      i + 1
    Wend
    If prime = #False : num + 1
    Else
    Break : EndIf
  ForEver
  ProcedureReturn num
EndProcedure

Probiers mal so aus, ich hab jetzt aber keine Geschwindigkeitstest gemacht!
Sollte aber schneller sein, schon allein weil ich kein Sqr() brauche...

Verfasst: **30.11.2008 17:50**

Also Du könntest z.B. erstmal die nächste ungerade Zahl ermitteln (If Int(zahl / 2) * 2 <> zahl), und von da an nur in Zweierschritten weiterlaufen, denn gerade Zahlen können sowieso keine Primzahlen sein (mal abgesehen von der 2).

Außerdem können sämtliche Zahlen, die hinten mit einer 5 enden, auch keine Primzahlen sein (abgesehen von der 5 selbst). Das kannst Du z.B. checken indem Du If Int(zahl / 5) * 5 <> zahl machst.

Mit diesen beiden Checks reduzierst Du den Suchraum schonmal auf 40%.

Gibt glaub noch ein paar mehr Regeln, z.B. mit Quersummen und sowas, aber da kenne ich mich jetzt auch nicht so gut aus. Gibt da z.B. Regeln wie man rausfinden kann, ob eine Zahl durch 3 teilbar ist usw.

Verfasst: **30.11.2008 21:31**

Quersumme durch 3 Teilbar...

Verfasst: **01.12.2008 14:28**

Man kann auch einfach eine kleine Liste der ersten Primzahlen in eine DataSection packen
und durch diese teilen bevor man in Zweierschritten durch die ungeraden Zahlen läuft.
Je größer diese kleine Liste wird, desto schneller geht's natürlich.

Verfasst: **01.12.2008 16:19**

Hier die Liste der Primzahlen von 2 bis 100.000:

=> Primzahlen von 2 bis 100.000

PureBoard

Schnell nächste Primzahl finden

Schnell nächste Primzahl finden