Primzahlen abspeichern

[Antagonist1337]

Hey Leute,
ich habe versucht mir ein kleines Programm zu schreiben welches mir Primzahlen mit einer bestimmten Anzahl von Stellen in eine Textdatei abspeichert.
Jedoch bleibt die Textdatei leer sobald die Anzahl der Stellen 5 überschreitet, da ich aber 100 stellige Primzahlen brauche bin ich leicht aufgeschmissen

Hier mal der Code:

Code: Alles auswählen

# Module importieren
import _thread, math

def getPrimes(xmax, digits):
    global x
    global l
    while x <= xmax:
        a = x
        x += 1
        for i in range(2, int(math.sqrt(a)+1)):
            if a % i == 0:
                break
            elif i == int(math.sqrt(a)) and len(str(a)) == digits:
                l.append(a)
    

# Hauptprogramm
l = []
x = 1
xmax = 100000
digits = 5

for y in range(0,4):
    _thread.start_new_thread(getPrimes, (xmax, digits))
    
l.sort()

file = open("primes.txt", "w")

for i in range(0, len(l)):
    file.write(str(l[i]) + "\n\n")
    
file.close()

Danke im Voraus für eure Hilfe!

Gruß Antagonist1337

[EyDu]

Hallo und willkommen im Forum!

An deinem Code ist eigentlich alles eine Katastrophe:
- statt _thread sollte threading verwendet werden
- einstellige Bezeichner
- globale Variablen
- undurchsichtige Schleifenkonstrukte
- die Berechnung der Primzahlen ist viel zu primitiv um das effizient zu machen (such mal im Forum)
- die Verwendung von Threads grenzt hier an Wahnsinn: es können bei dir doppelte Einträge entstehen, die fehlende Sortierung hast du ja selber bemerkt und Threads arbeiten und Python auch nicht parallel; du hast dein Programm also fehlerhaft und langsamer zugleich gemacht (deshalb testet man seine Änderungen und "Optimierungen")
- ``for i in range(len(liste)): element = liste`` ist ein Antipattern und lässt sich viel besser als ``for element in liste: ...``schreiben
- Strings solltest du nicht mit + zusammensetzen, schau dir mal String Formatting an
- Dateien sollten mit dem with-Statement geöffnet werden, dann muss man sich nicht um das Schließen kümmern.

Das solltest du erstmal alle ausbessern, bzw. gleich komplett neu schreiben. Ohne Threads. Sonst hat das alles keinen Sinn.

Zu deinem eigentlichen Problem: hast du den Code selber geschrieben? Hier ist doch wirklich mehr als offensichtlich warum nur fünstellige Zahlen genommen werden. Das steht sogar explizit im Code drin.

[Antagonist1337]

Der Code mal außen vor... wenn ich digits erhöhe und natürlich den Bereich in dem es arbeiten soll dann wird es nicht mehr abgespeichert. Dass die Methode primitiv ist ist mir bewusst jedoch kann ich schlecht die Methode des Siebs des Erasthones verwenden da ich für 155stellige Primzahlen leider nicht genügend Systemressourcen habe. Ja ich habe den Code selbst geschrieben. Normalerweise Programmiere ich nicht Python an dem Code sieht man warum... in C++ reichen jedoch die Wertebereiche nicht aus um 155stellige Primzahlen zu erhalten. In C++ würde ich mich auch unterstehen globale Variablen zu verwenden jedoch sind mir Zeiger in Python leider völlig unbekannt....

[EyDu]

Das du so niemals bei einer 155-stelligen Zahl ankommen wirst ist doch klar. Bis 10^155 zählen dauert halt ein wenig (sehr) lange, auch wenn du tausende Kerne parallel rechnen lässt. Und dann zählst du natürlich (im schlimmsten Fall) bei jeder Zahl n noch bis n^0.5. Du befindest dich quasi auf dem halben Weg zur quadratischen Laufzeit und das für sehr große Zahlen. Ich würde versuchen mir die Zahlen online irgendwo zu besorgen, sonst steckst du viel Arbeit in nichts.

Auch in C++ würde man nicht so programmieren wie du es hier machst, die Hälfte meiner Punkte ist von der Programmiersprache unabhängig.

[pillmuncher]

Wieso verwendest du _thread? Das ist ein low-level Hilfs-Modul, das bloß zur Implementation des high-level-Moduls threading verwendet wird, welches du benutzen solltest. Aus mehreren Thread heraus ohne Mutex auf eine globale Datenstruktur halte ich allerdings für mutig.

Desweiteren: in Python gibt es glücklicherweise keine Zeiger. Man braucht aber auch idR. keine globalen Daten. In deinem Beispiel genügt eine Generator-Funktion:

Code: Alles auswählen

from math import sqrt


def make_primes(xmax, digits):
    for x in xrange(1, xmax + 1):
        sqrx = int(sqrt(x))
        for i in xrange(2, sqrx + 1):
            if x % i == 0:
                break
            elif i == sqrx and len(str(x)) == digits:
                yield x


if __name__ == '__main__':

    with open('primes.txt', 'w') as primes_file:
        format_line = '{0}\n'.format
        primes_file.writelines(
            format_line(prime) for prime in make_primes(1000000, 6))

Ich hab den Bereich mal für 6 Digits eingerichtet und es scheint zu funktionieren. Die Stelle im Code, auf die EyDu Bezug nimmt, wenn er schreibt, dort stünde, warum es nur mit fünfstelligen Zahlen funktionieren würde, sehe ich allerdings nicht. Wahrscheinlich übersehe ich da was.

[EyDu]

Die Stelle im Code, auf die EyDu Bezug nimmt, wenn er schreibt, dort stünde, warum es nur mit fünfstelligen Zahlen funktionieren würde, sehe ich allerdings nicht. Wahrscheinlich übersehe ich da was.

Code: Alles auswählen

xmax = 100000
digits = 5

Aber auch der Generator wird nicht für 155-stellige Zahlen funktionieren. Theoretisch natürlich schon.

[EyDu]

Dann mache ich mal einen Doppelpost: Warum brauchst du so große Primzahlen? Ich würde einfach mal auf Kryptographie tippen. Reichen vielleicht schon Pseudoprimzahlen oder eine hohe Wahrscheinlichkeit, dass es sich um eine Primzahl handelt, aus? Oder brauchst du einfach nur irgendwelche großen Primzahlen?

[Antagonist1337]

Ja ich benötige sie für die Krypotographie. Es müssen eigentlich Primzahlen sein.
Wie gesagt wenn ich kleinere Primzahlen bräuchte hätte ich den Sieb des Erasthones verwendet welcher natürlich viel effektiver wäre jedoch bräuchte ich dafür eine Array von 2 bis zu der Zahl die ich benötige und bei bestem willen wenn ich 1e155 bestandteile einer array hab reichen meine Systemressourcen nicht aus ich weiß ja nicht was für einen Server du daheim rumstehen hast...
Warum ich _thread benutze? Weil in einem alten Programmierbuch welches ich von einem Kumpel geliehen habe eben steht, dass man Multithreading so benutzt in Python! Besten dank an "Python für Anfänger" von Thomas Theis.
Nochmal für alle:
Wenn ich 155 stellige Primzahlen will ist mein x bei 1e154, mein xmax bei 1e156 und meine digits bei 155! Die Werte sind lediglich zum testen da, damit das Programm keine Stundenlangen Berechnungen ausführt bevor ich überhaupt sehe ob alles klappt! Es funktioniert auch alles Prima bis ich alles auf mehr als 5 digits einstelle.
Danke übrigens an pillmuncher für einen funktionierenden Code. Ich werde ihn nicht einfach kopiern ich werd ihn erst verstehn... Trotzdem jetzt als Nebenfrage wieso genau funktioniert mein Code nicht?

[EyDu]

Wenn ich 155 stellige Primzahlen will ist mein x bei 1e154, mein xmax bei 1e156 und meine digits bei 155! Die Werte sind lediglich zum testen da, damit das Programm keine Stundenlangen Berechnungen ausführt bevor ich überhaupt sehe ob alles klappt!

Klar, aber selbst hier wirst du es nicht schaffen alle Zahlen von 10^154 bis 10^155 - 1 zu testen. Das liegt ja noch immer in der Größenordnung von 10^155 Tests. Selbst wenn alle Siebenmilliarden Menschen ihren Rechner mit 1024 Kernen rausholen welcher (völlig unrealistisch) Viermilliarden Primzahltests pro Sekunde durchführen kann, dann brauchst du noch immer so um die 10^126 Jahre bist du alle Primzahlen gefunden hast. (Wenn man es so umgesetzt hat wie du: testen jeder Zahl und ohne Speichern). Mit Streichen der ungeraden Zahlen sogar doppelt so schnell ^^

[BlackJack]

@Antagonist1337: Kryptographie funktioniert doch gerade deswegen so gut weil das was Du da vorhast nicht effizient machbar ist. Also auch nicht für richtig grosse Rechner oder gar Cluster.

Es gibt Wege grosse Zahlen zu erzeugen, die mit sehr hoher Wahrscheinlichkeit Primzahlen sind, *ohne* dass man tatsächlich alle Primzahlen bis in diese Grössenordnungen erzeugen muss. Und genau diese Wege werden von Kryptographie-Software auch benutzt.

Also lies Dich in diese Verfahren ein. Und vielleicht auch noch am Rande mal in den Unterschied zwischen effektiv und effizient.

[EyDu]

Ich weiß dass es dafür keine effiziente Methode gibt aber EyDu kritisiert mich dafür dass ich keine effiziente nutze?...

Ich habe deine Methode kritisiert, weil sie unter alle Umständen einer der ineffizientesten Umsetzungen ist, auch schon bei sehr kleinen Zahlen. Das ist also eher allgemeiner Natur.

Wenn du weißt, dass es (vermutlich) keine verünftige Lösung gibt, warum versuchst du dann eine zu implementieren?

[Antagonist1337]

Ich versuche überhaupt eine zu implementieren damit ich auf ein paar 155 stellige Primzahlen komme die Methode ist mir dabei recht egal solang ich auf ein paar Zahlen komme.. das Programm an sich werde ich definitiv besser umsetzen aber das Programm ist nur Mittel zum Zweck

[Hyperion]

Dann schau doch mal hier rein. Damit findest Du verschiedene Ansätze, die Dir weiterhelfen.

(Hui, den Miller-Rabin-Test hatte ich doch schon wieder glatt vergessen, obwohl meine Crypto-Prüfung erst fast genau ein Jahr her ist )

[jerch]

Für kleinere Werte funktioniert eine Mischung aus Sieb und Miller-Rabin-Test ganz gut:

- Erstellung einer unteren Primzahlliste mittels Sieb
- Filterung aller Vielfache der Primliste aus Deinem Wertebereich (hier kannst Du nicht einfach sieben, da Dein Wertebereich zu groß ist, Möglichkeit wäre, einen Offsetindex mitzuführen und dessen Teilbarkeit gegen Primzahl xy zu testen)
- Verbleibende sind primzahlverdächtig
- teste Verbleibende auf pseudoprim mittels Miller-Rabin
- Pseudoprime genau testen (gegen alle Primzahlen bis Quadratwurzel)

Der Miller-Rabin sorgt für eine deutliche Reduzierung der wirklich zu testenden Zahlen (letzter und rechenintensivster Schritt). Allerdings dürfte Dir für Deinen Wertebereich immernoch die Rechenzeit/Speicher um die Ohren fliegen (selbst auf einer 128bit-Maschine ).

[jerch]

NB: Falls Dir starke Pseudoprimzahlen reichen, kannst Du nach dem Miller-Rabin-Test aufhören. Das empfielt selbst Herr Schneier und wird wohl auch von den üblichen Krypto-Implementationen so gehandhabt. Für etwas mehr Sicherheit könntest Du noch den Solovay-Strassen-Test nachschalten, da beide orthogonal sind.