Algorithmus zur Primzahlenfindung

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von Yanbel.

    Algorithmus zur Primzahlenfindung

    Hallo Leute,

    ich benötige einen leistungsstarken Algorithmus zur Findung von Primzahlen. Bisher verwende ich folgenden Programmcode, aber den habe ich mir vor Jahren mal ausgedacht und hoffe jemand kennt eine schnellere Variante:

    Code

    VB.NET-Quellcode

    1. Private Primzahlenliste As New List(Of Integer)
    2. Private Teilerliste As New List(Of Integer)
    3. Private Sub PrimzahlenBerechnung (Zielzahl As Integer)
    4. Teilerliste = New List(Of Integer) From {2, 5}
    5. Primzahlenliste = New List(Of Integer) From {2, 5}
    6. Dim Primzahl As Boolean = True
    7. Dim WurzelZiel As Integer = Math.Ceiling(Math.Sqrt(Zielzahl))
    8. For i = 2 To Zielzahl
    9. Primzahl = True
    10. Select Case True
    11. Case i Mod 2 = 0 OrElse i.ToString.EndsWith("5")
    12. Primzahl = False
    13. Continue For
    14. Case Else
    15. For Each x In Teilerliste
    16. If i Mod x = 0 Then
    17. Primzahl = False
    18. Exit For
    19. End If
    20. Next
    21. End Select
    22. If Primzahl Then
    23. Primzahlenliste.Add(i)
    24. If i < WurzelZiel Then
    25. Teilerliste.Add(i)
    26. End If
    27. End If
    28. Next
    29. End Sub


    Die Umsetzung erfolgt mit LINQ, das Beispiel mit den For-Schleifen dient der Veranschaulichung.


    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.

    Yanbel schrieb:

    VB.NET-Quellcode

    1. For i = 2 To Zielzahl
    2. ' ...
    3. Case i Mod 2 = 0 OrElse i.ToString.EndsWith("5")
    Da hast Du schon Deine Zeitfresser.
    Die 2 hast Du bereits gelistet, in der Schule haben wir gelernt, dass 2 die einzige grade Primzahl ist.
    Also machst Du so eine Schleife:

    VB.NET-Quellcode

    1. For i = 3 To Zielzahl Step 2
    Wenn Du eine Zahl testest, indem Du ihre Stringrepräsentation bemühst, ist das absolut grottenschlecht.
    Dafür gibt es die Modulo-Funktion, die Du ja bereits auf die Zahl 2 anwendest.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Du kannst auch die zahl binär darstellen und die letzte stelle immer auf 1 setzen... Somit ist die zahl immer ungerade.

    Wenn die zahl 512bit haben soll... Fullst die stellen zufällig mit 1 und 0 und die letzte stelle ist immer einer 1.

    Anschließend musst du diese zahl prüfen ob es eine primzahl ist... Hier gibt es verschiedene möglichkeiten... Schau am besten mal nach primzahltest (bsp. Miller rabbin)

    Auch interessant :
    de.m.wikipedia.org/wiki/Sieb_des_Eratosthenes
    NETworkManager - A powerful tool for managing networks and troubleshoot network problems!
    @Yanbel

    Vielleicht könntest du ja noch genau beschreiben was du den wirklich willst.
    Willst du alle Primes von 3 bis x (z.B. Int32.MaxValue), oder suchst du x-beliebige Primes im Integer Bereich.

    Für alle Primes von 3 bis x nimm den Sieb des Eratosthenes (Link wurde erwähnt)
    Wenn du x-beliebige Primes suchst dann kann ich den Miller Rabin Test empfehlen.
    de.wikipedia.org/wiki/Miller-Rabin-Test

    Zweitere würde auch mit dem Sieb des Eratosthenes gehen. Es braucht einfach seine Zeit, bis er die geladen hat. Besser wäre hier wahrscheinlich das Segmentiertes Sieb von Eratosthenes. Es lohnt sich (Lerneffekt ist hoch) auf jeden Fall alle Varianten durchzuarbeiten.

    Freundliche Grüsse

    exc-jdbi
    Hey Leute vielen Dank schon mal für die diversen Rückmeldungen.

    @RodFromGermany: Die Umstellung auf Mod hat schon mal 10 Sekunden Einsparung bei 1 - 10.000.000. gebracht.

    @ErfinderDesRades: Danke für deine Ideen, aber das Beispiel Miller-Rabin ist scon ein gutes Beispiel, warum ich von solchen Algorthmen absehe. Problematisch bei Monte-Carlo-Algorithmen ist, dass sie (zwar mit einer geringen Wahrscheinlichkeit) falsch-positive Ergebnisse liefern. Ich benötige aber eine bereinigte Liste, weshalb ich inperformante deterministische Algorithmen verwenden muss.

    @BornToBeRoot: Gute Idee. Aber leider (DotNet verschuldet) inperformant, da Binärwerte zur weiteren Verarbeitung bereits in Dezimalwerte umgewandelt werden. Eine weitere Umwandlung zurück in einen Binärwert geht auf die Performance.

    @exc-jdbi Im Prinzip basiert der oben beschriebene Algorithmus auf dem Sieb des Eratothenes, mit dem Unterschied, dass ich nicht alle Vielfachen der vorangegangenen Primzahlen "aussiebe", sondern nur alle vorangegangenen Primzahlen die kleiner oder gleich der Wurzel des Maximalwertes sind. Dein Beitrag hat mich allerdings auf die Idee gebracht, dass ich die Teilerliste erst dann erweitern muss, wenn Wurzel(i) >= der zu vergleichenden Primzahl ist, was den Abgleich deutlich beschleunigt, da weniger Abgleiche gemacht werden müssen. Vielen Dank dafür. Ich habe mich mit den gängigen Algorithmen beschäftigt, aber wie bereits gesagt, kommen nicht-deterministische Algorithmen für mich nicht in Frage. ;)

    Hier der neue angepasste Code

    Code

    VB.NET-Quellcode

    1. Private Function GetPrimzahlen(ZielWert As Integer) As List(Of Integer)
    2. Dim Primzahlenliste As New List(Of Integer)
    3. Teilerliste = New List(Of Integer)
    4. Dim MaxTeiler As Integer = Math.Ceiling(Math.Sqrt(ZielWert))
    5. Dim NextTeiler As Nullable(Of Integer) = 2
    6. For i = 2 To ZielWert
    7. Primzahlenliste.Add(i)
    8. Next
    9. Primzahlenliste = Primzahlenliste.Where(Function(n) (n Mod 2 <> 0 OrElse n = 2) AndAlso (n Mod 5 <> 0 OrElse n = 5)).ToList
    10. Teilerliste = Primzahlenliste.Where(Function(n) n <= MaxTeiler).ToList
    11. Primzahlenliste = Primzahlenliste.Where(Function(n)
    12. If NextTeiler IsNot Nothing AndAlso n >= NextTeiler Then
    13. NextTeiler = GetNextTeiler()
    14. End If
    15. AktiveTeilerliste = Teilerliste.Where(Function(y) y <= Math.Sqrt(n)).ToList
    16. Return AktiveTeilerliste.Where(Function(y)
    17. Return n Mod y = 0 AndAlso n <> y
    18. End Function).Count = 0
    19. End Function).OrderBy(Function(n) n).ToList
    20. Return Primzahlenliste
    21. End Function
    22. Private Function GetNextTeiler() As Nullable(Of Integer)
    23. If z < Teilerliste.Count Then
    24. AktiveTeilerliste.Add(Teilerliste(z))
    25. z += 1
    26. Return (Math.Pow(Teilerliste(z), 2))
    27. Else
    28. Return Nothing
    29. End If
    30. End Function




    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „Yanbel“ ()

    Hallo @Yanbel

    Der Sinn und der Zweck von SOE ist ja das nur bis zur Sqrt(max) hochgearbeitet wird, weil alle anderen mit dem Produkt des Inkrements auf True bzw. False (je nachdem wie es angewendet wird) gesetzt werden.

    Wenn ich einen Tip geben darf. Versuchs zuerst ohne LINQ.

    Erstell dir zuerst mal eine ganz naive Methode mit BitArray wie SOE aufgebaut ist. Nachher, wenn das funktioniert und optimiert ist mit LINQ anfangen. LINQ hat ein paar ganz gute Sachen, wie z.B. die Aggregate-Methode, in der man eine Aufzählung und gleichzeitig eine Funktion einbauen kann.

    Ich würde mal so anfangen

    VB.NET-Quellcode

    1. Private Function NaiveSieveSoE() As Int32()
    2. Dim bits As New BitArray(MAXNUMBER + 1, True)
    3. bits(0) = False : bits(1) = False
    4. Dim i = 4I, j = 0I
    5. While i <= MAXNUMBER
    6. bits(i) = False : i += 2
    7. End While
    8. i = 3I
    9. 'Die Grundlage ist geschaffen jetzt der eigentliche Teil
    10. End Function


    EDIT: Kleine Korrektur

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „exc-jdbi“ ()

    exc-jdbi schrieb:

    Wenn ich einen Tip geben darf. Versuchs zuerst ohne LINQ.


    So habe ich ursprünglich angefangen und dann auf LINQ umgestellt. Ich gehe jetzt nicht wieder einen Schritt zurück. Mein Code funktioniert und ist auch schnell. Ich habe gehofft, dass vielleicht noch jemand einen guten neuen Ansatz hat, den ich erstens noch nicht bedacht habe, zweitens, der nicht auf die Qualität der Ergebnisse schlägt und drittens auch nichts mit den herkömmlichen Algorithmen zutun hat, da ich mich mit denen auch schon beschäftigt habe. Mein Code macht jetzt schon nichts anderes als das SoE.

    LINQ Aggregate-Funktion ist ein gutes Stichwort, bringt aber nicht die Performance-Verbesserung, die ich mir erhofft habe.

    Den Quellcode oben hab ich nochmal angepasst, da er noch einen performancelastigen Fehler hatte:

    Code

    VB.NET-Quellcode

    1. Private Primzahlenliste As New List(Of Integer)
    2. Private AktiveTeilerliste As New List(Of Integer)
    3. Private MaxTeiler As Integer
    4. Private z As Integer = 0
    5. Private Function GetPrimzahlen(ZielWert As Integer) As List(Of Integer)
    6. Primzahlenliste = New List(Of Integer)
    7. MaxTeiler = Math.Ceiling(Math.Sqrt(ZielWert))
    8. Dim NextTeiler As Nullable(Of Integer) = 0
    9. Dim isNotPrime As Boolean = False
    10. For i = 2 To ZielWert
    11. Primzahlenliste.Add(i)
    12. Next
    13. Primzahlenliste = Primzahlenliste.Where(Function(n) (n Mod 2 <> 0 OrElse n = 2) AndAlso (n Mod 5 <> 0 OrElse n = 5)).ToList
    14. Primzahlenliste = Primzahlenliste.Where(Function(n)
    15. If NextTeiler IsNot Nothing AndAlso n >= NextTeiler Then
    16. NextTeiler = GetNextTeiler()
    17. End If
    18. isNotPrime = False
    19. Return AktiveTeilerliste.Where(Function(y)
    20. If Not isNotPrime Then
    21. If n Mod y = 0 AndAlso Not n = y Then
    22. isNotPrime = True
    23. Return True
    24. Else
    25. Return False
    26. End If
    27. Else
    28. Return False
    29. End If
    30. End Function).Count = 0
    31. End Function).OrderBy(Function(n) n).ToList
    32. Return Primzahlenliste
    33. End Function
    34. Private Function GetNextTeiler() As Nullable(Of Integer)
    35. If z < MaxTeiler Then
    36. AktiveTeilerliste.Add(Primzahlenliste(z))
    37. z += 1
    38. If z < MaxTeiler Then
    39. Return (Math.Pow(Primzahlenliste(z), 2))
    40. Else
    41. Return Nothing
    42. End If
    43. Else
    44. Return Nothing
    45. End If
    46. End Function



    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Yanbel“ ()

    Eierlein schrieb:


    Spoiler anzeigen

    VB.NET-Quellcode

    1. Module Module1
    2. Sub Main()
    3. Dim anz As Integer = 100
    4. Dim j As Long
    5. Dim b(anz) As Byte
    6. For i As Integer = 2 To anz
    7. If b(i) = 0 Then
    8. Debug.Print(i)
    9. For j = i * i To anz Step i
    10. b(j) = 1
    11. Next
    12. End If
    13. Next i
    14. End Sub
    15. End Module


    Sehr geil... sowas habe ich gesucht. Einziges Problem: Wenn ich Primzahlen suche die größer sind als eine Milliarde frisst sich der Arbeitsspeicher voll, aber das Problem kriege ich in den Griff. Vielen Dank dafür. Thread wird geschlossen.


    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.
    @Yanbel

    Alle Primes bis einer Milliarde in eine Array zu schaufeln ist unsinnig. Dafür bietet sich genau das Segmentierte Sieb von Eratosthenes an.
    D.h. man musst sich nur um die Primes bis ca. 31620 (Wurzel von 1E9) kümmern, und die sind mit dem Algo von Eierlein in "nullkommanichts" hergestellt, auch wenn dieser Algo noch lange nicht optimiert ist.

    Das einzige was ein bisschen an Performance frisst ist das immer wieder neue Sieben des gewünschten Segmentbereiches. Der Vorteil jedoch ist, dass die Array in dem die Primes gehalten werden nur so gross ist wie die Segmentbreite (daher auch Segmentiertes Sieb von Eratosthenes). Und somit ist es auch kein Ressourcenfresser.

    Freundliche Grüsse

    exc-jdbi

    exc-jdbi schrieb:


    Das einzige was ein bisschen an Performance frisst ist das immer wieder neue Sieben des gewünschten Segmentbereiches. Der Vorteil jedoch ist, dass die Array in dem die Primes gehalten werden nur so gross ist wie die Segmentbreite (daher auch Segmentiertes Sieb von Eratosthenes). Und somit ist es auch kein Ressourcenfresser.


    Das mag in der Theorie stimmen, aber in der Praxis ist die Arbeitsspeicherbelegung bei 1 - 1.000.000.000 im Visual Studio kurz vor Ende der Ausführung bei knapp 1,2 GB. Wenn ich jetzt noch eine 0 dranhänge wirft er eine SystemOutOfMemory Exception. Bisher habe ich auch noch nicht so richtig verstanden wieso, denn wie du schon sagtest, dürfte das eigentlich nicht passieren.


    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.
    @Yanbel Stell Deine Applikation um auf x64, da kann sie wesentlich größere Arrays.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @Yanbel

    Sorry, aber ich muss jetzt nochmals fragen. Für was werden die Primes den gebraucht? Eine Frage die bis jetzt noch nicht beantwortet wurde.
    Wenn es für einen Zufalls-Prime-Generator ist, dann ist es vielleicht sinnvoll die Primes abzuspeichern, sofern das Maximum nicht all zu hoch liegt.

    Anders wenn die Primes immer wieder neu Produziert werden müssen. Daher auch die Frage wie hoch willst du mit dem Maximum. Auch das ist noch nicht beantwortet. Weil wenn du noch höher willst als die 1Milliarde, dann ist es schon fast ein Muss mit dem Segmentierte Sieb von Eratosthenes zu arbeiten. (Ok, mit dem BigInteger und Miller-Rabin ist auch noch vieles möglich, das müsste man jetzt testen).

    Ein Beispiel für das Verständnis vom Segmentierte Sieb von Eratosthenes
    Wenn ich meinen optimierten naiven PrimeEoS laufen lasse, so hat er, sagen wir für die 78498 (bis 1Mio) ein paar Millisekunden, und mein Compy ist definitiv keine Leistungsmaschine. Die letzte Prime ist also 999983. Wenn ich die Quadriere komme ich auf 9.999 * 10^11 (also rund 1E12), was der Maximalzahl entsprechen würde. Mit dem Segmentierte Sieb von Eratosthenes ein Kinderspiel, jedoch nur Segmentweise. Wenn also deine Segmentbreite 1000 ist, definierst du irgend ein "segment = min 1000" oder anders herum irgend ein "segment = max - 1000", Hauptsache das max überschreitet nicht deinen Maximalwert von 1.999 * 10^11. Nach dem Absuchen des Segmentes hast du sicher immer ein paar Primes in deiner Array, weil Primelüggen von 1000 eher bei noch höheren Zahlen liegen.

    Und somit taugt der Segmentierte Sieb von Eratosthenes für viele Sachen, nur für eines nicht, wenn wirklich alle Primes bis zum Maximum präsent sein müssen. Weil für das ist der Segmentierte Sieb von Eratosthenes nicht gedacht.

    Abschätzen für welchen Zweck oder für welche Tätigkeit musst du es schlussendlich.

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    @RodFromGermany: Auch bei 64-Bit-Anwendungen ist der Index eines Array ein Integer-Wert, womit die technische Limitierung eines Arrays im DotNet bei Int.MaxValue liegt unabhängig von CPU-Architektur.

    @exc-jdbi: Grober Anwendungsbereich: Asymetrische Verschlüsselungsverfahren, speziell Key-Generierung. Die Primzahlen müssen also fortwährend neu generiert werden. Natürlich speichere ich die gefundenen Ergebnisse in einer Datenbank zwischen, aber das hilf mir nicht bei der Findung neuer Primzahlen. Und bringt mich auch der Code von Eierlein nur bedingt weiter, denn der eignet sich nur für Primzahlen von 1 bis 1 Milliarde zu gebrauchen, aufgrund der technischen Limitierung. Also genau die Größe von Primzahlen, die ich nicht gebrauchen kann, da ich bedeutend größere Primzahlen suche.


    Ein Computer wird das tun, was du programmierst - nicht das, was du willst.