Anzeige
Seite 1 von 7 123 ... LetzteLetzte
Ergebnis 1 bis 10 von 64

Thema: Sieb des Eratosthenes

  1. #1
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard Sieb des Eratosthenes

    Anzeige
    Hallo zusammen,

    ich beschäftige mich zur Zeit privat etwas mit der Programmierung des Siebes des Eratosthenes.

    Allen Mathe- und Primzahl-Freunden wird das altbekannt sein, aber wer hat sich schon mal an die Programmierung desselben gewagt? Diejenigen, die das schon mal gemacht haben wissen, dass das recht schnell zu Speicherproblemen führen kann, wenn man damit auch Primzahlen mit mehr als zehn Stellen berechnen will.

    Ein Blick auf den Pseudocode des WP-Artikels zeigt, dass auch dort von allen natürlichen Zahlen bis zum gewünschten Limit ausgegangen wird und das benötigt dann schnell auch sehr viel Speicher.

    Meine Idee lautet nun, dass man die Startmenge an möglichen Zahlen vorab sinnvoll verkleinert. So kann man bei der Suche nach Primzahlen vorab trivialerweise alle geraden Zahlen streichen und reduziert damit die Größe des Siebes bereits um 50% !.

    Das Sieb wird in diesem ersten Schritt also durch die Reihe

    2 * n + 1

    definiert, wobei n wieder in der Menge der natürlichen Zahlen größer oder gleich eins liegt.

    Streicht man vorab die Vielfachen von 3, so erhält man nach relativ einfacher Rechnung die zwei Reihen:

    6 * n + 1
    6 * n + 5

    wiederum mit n = 1, 2, 3, ...

    streicht man weiter die Vielfachen von 5 erhält man die folgenden acht Reihen:

    2*3*5 * n + 1
    2*3*5 * n + 7
    2*3*5 * n + 11
    2*3*5 * n + 13
    2*3*5 * n + 17
    2*3*5 * n + 19
    2*3*5 * n + 23
    2*3*5 * n + 29

    wiederum mit n = 1, 2, 3, ...

    usw. und man erkennt dann auch, wie dieses Schema prinzipiell immer weiter fortgeführt werden kann. Man erhält auf diese Weise also immer bessere "übervollständige" Primzahlgeneratoren. Die D.h. die genannten Reihen produzieren immer alle Primzahlen, enthalten allerdings aber auch mehr oder weniger zusätzliche Zahlen, die nicht prim sind.

    Über diese "Vorsiebung" kann man nun den benötigten Speicherplatz bei der Programmausführung für das vollständige Sieb stark reduzieren und ich würde nun gerne wissen, ob einer der Autoren oder Leser hier so etwas schon mal gemacht hat oder noch bessere Tricks zum Sieb des Eratosthenes kennt.
    Freundliche Grüße, B.

  2. #2
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Beschränkt man sich nur auf ungerade Zahlen kann man den Speicherbedarf eines Programmes bereits deutlich reduzieren (< 500 MB anstelle < 1GB) und kann innerhalb des Wertebereiches des Datentyps long (32 Bit) ohne nennenswerte Rechenzeit (< 1 Minute) immerhin alle Primzahlen < x = 1e9 berechnen.

    Die komplizierteren Formeln bringen mMn keine nennenswerten Vorteile, weil das Programm dadurch deutlich unübersichtlicher wird und die Reduzierung von Speicherbedarf und Rechenzeit vergleichsweise gering bleiben.

    Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10. Dazu gibt es dann auch weiterführende Literatur, wie zB: https://primes.utm.edu/howmany.html
    Geändert von Bernhard (09.01.2022 um 02:01 Uhr)
    Freundliche Grüße, B.

  3. #3
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    Interessant erscheint mir dagegen die Berechnung der Primzahlfunktion für die Werte x >= 1e10.
    Halo Bernhard,

    was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

    Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.

    Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt. Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.

    Praktisch war auch, dass - da ich ja die kleinste von denen gesucht habe - ich an der Uni alle verfügbaren Rechner über das Wochenende in benachbarten Zahlenintervallen laufen lassen konnte, das ganze so abgeschätzt, dass meine Berechnungen am Montag früh um 6 Uhr abgeschlossen waren, damit dann die ersten Studenten nicht blockiert waren. Die Ergebnisse habe ich in einer Datei verspeichert und diese dann am Montag in der Mittagspause ausgedruckt. Somit ergaben sich verschiedene Kandidaten für g(n) und der absolut-kleinste war dann die gesuchte Zahl. Hierbei ist noch anzumerken, dass bei grösseren Zahlen pro Zehnerpotenz vielleicht 3 Hits zu erwarten sind, d.h. mit einer Ausnahme war jedesmal die gefundene Zahl schon das gesuchte Minimum, und in den allermeisten Fällen gab es keine Hits.


    Freundliche Grüsse, Ralf

  4. #4
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Hallo Ralf,
    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.

    Dann musst Du zwar die vier Grundrechenarten selber programmieren, aber im Falle der Addition und Subtraktion ist das sehr einfach und bei der Division machst Du das eben so wie man von Hand dividiert, d.h. die nächste noch nicht berücksichtigte Stelle "hinunterziehen" und dann die "Zwischensumme" dividieren.
    interessant, aber mittlerweile geht das mMn einfacher, wenn man gleich in Python programmiert. Dort kann man direkt mit beliebig großen ganzen Zahlen rechnen, solange man ausreichend Speicher hat.

    Damit kann man dann die Menge an Primzahlen sicher nochmal vergrößern, allerdings kommt dann auch die Frage, was man mit dieser Liste überhaupt anfangen kann.

    Erstaunlich auf jeden Fall, wie mächtig das "alte Sieb" ist.

    Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.
    Klar. So eine Tabelle, bzw. Array wird auch schon beim Sieb des Eratosthenes benötigt. Will man möglichst viele Primzahlen berechnen, wird diese Tabelle dann schnell sehr groß, so dass erneut der verfügbare Speicher die Menge an Primzahlen begrenzt.

    Damals ging es mir um die Fragestellung, wie viele Primzahlen ich von einer geraden natürlichen Zahl abziehen kann und das Ergebnis ist jedesmal eine Nicht-Primzahl. Also konkret um die Funktion g(n) = kleinste gerade natürliche Zahl, von der man die ersten n Primzahlen subtrahieren kann und das Ergebnis ist eine Nicht-Primzahl.
    War das eine Übung, oder gibt es dafür eine weitere Anwendung?

    BTW: Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt und werden bei der Berechnung sehr großer Primzahlen verwendet. Was bieten die Zahlen 2^n + 1? Gibt es dazu keinen effektiven Primzahltest?
    Geändert von Bernhard (09.01.2022 um 21:53 Uhr)
    Freundliche Grüße, B.

  5. #5
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    War das eine Übung, oder gibt es dafür eine weitere Anwendung?
    Hallo Bernhard,

    hätte ich diese "Übung" gelöst, so hätte ich die Fields-Medaille bekommen. Die Aufgabenstellung ist äquivalent zur Goldbach'schen Vermutung, deswegen auch meine Wortwahl g(x).


    Freundliche Grüsse, Ralf

  6. #6
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    Die Zahlen 2^n - 1 werden Mersenne-Zahlen genannt
    Hallo zusammen,

    hierzu gibt es eine schöne Anekdote über Frank Nelson Cole, die wir im Studium gelernt haben und die auch in der Wikipedia dokumentiert ist:

    Im Jahre 1903 präsentierte er bei einem Treffen der American Mathematical Society in einem ungewöhnlichen Vortrag die Faktoren der Mersenne-Zahl 267-1 (kurz M67). Bereits 1876 hatte Édouard Lucas gezeigt, dass diese Zahl, entgegen der Angabe von Marin Mersenne, keine Primzahl ist. Primfaktoren dieser Zahl blieben aber unbekannt.

    Bei seinem Vortrag ging Cole wortlos zur Tafel und berechnete den Wert von M67. Sodann schrieb er auf die andere Tafelseite die Aufgabe 193.707.721 · 761.838.257.287. Er führte die langwierige Multiplikation handschriftlich aus und zeigte am Schluss, dass beide Berechnungen zum gleichen Ergebnis von 147.573.952.589.676.412.927 führten. Ohne ein Wort gesprochen zu haben, ging Cole an seinen Platz zurück, während seine Kollegen aufstanden und ihm applaudierten.
    Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

    Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.

    Ohne ein Wort gesprochen zu haben erhebt sich die gesamte Zuhörerschaft und spendet standing ovations, denn sie wissen natürlich ganz genau, was Cole in diesem Moment bewiesen hat, und natürlich haben sie schon vorher bereits nach der 1.Zeile geahnt, dass Cole das nun beweisen wird, was er dann auch tat.


    Freundliche Grüsse, Ralf

  7. #7
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    was Du hier machen kannst ist Zahlen mit Hilfe zweier Varialen zusammenzusetzen, d.h. die ersten 10 Stellen eines Primzahlkandidaten in einer Variablen und die anderen 10 Stellen in der anderen Variablen.
    Hast Du das bei Deinem damaligen "Goldbach-Projekt" verwendet? Falls ja, waren die Zahlen also vermutlich auf 20 Stellen begrenzt.
    Freundliche Grüße, B.

  8. #8
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Ausserdem kann man, falls man aus irgendeinem Grunde gewisse Primzahlen immer wieder neu ermitteln muss, diese in einer Tabelle zwischenspeichern und dann nur die Tabelle durchgehen, das hat damals meine Berechnung wesentlich beschleunigt.
    Zur Abschätzung der Größe einer solchen (Hilfs-)Tabelle ist wieder die Primzahlfunktion hilfreich.
    Freundliche Grüße, B.

  9. #9
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Man muss sich das einmal vorstellen: da geht einer zur Tafel, spricht kein Wort und subtrahiert 1 von einer Zweierpotenz.

    Danach geht er weiterhin wortlos zur anderen Tafelhälfte und multipliziert dort zwei Zahlen. Das ist übrigens Grundschulmathematik.
    In diesem Vortrag waren sicher fast ausnahmlos echte Zahlenfreunde anwesend.

    Die genannte Primfaktor-Zerlegung von M(67) schafft ein kurzes Python-Script heute in maximal einer Minute Rechenzeit.
    Geändert von Bernhard (10.01.2022 um 12:06 Uhr) Grund: typo
    Freundliche Grüße, B.

  10. #10
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Anzeige
    Zitat Zitat von Bernhard Beitrag anzeigen
    Hast Du das bei Deinem damaligen "Goldbach-Projekt" verwendet? Falls ja, waren die Zahlen also vermutlich auf 20 Stellen begrenzt.
    Lieber Bernhard,

    wir haben damals auf dem Apple II mit PASCAL programmiert und der Datentyp INTEGER ging bis 2^15 - 1, also bis 32767


    Freundliche Grüsse, Ralf
    Geändert von ralfkannenberg (10.01.2022 um 12:02 Uhr)

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  
astronews.com 
Nachrichten Forschung | Raumfahrt | Sonnensystem | Teleskope | Amateurastronomie
Übersicht | Alle Schlagzeilen des Monats | Missionen | Archiv
Weitere Angebote Frag astronews.com | Forum | Bild des Tages | Newsletter
Kalender Sternenhimmel | Startrampe | Fernsehsendungen | Veranstaltungen
Nachschlagen AstroGlossar | AstroLinks
Info RSS-Feeds | Soziale Netzwerke | Flattr & freiwilliges Bezahlen | Werbung | Kontakt | Suche
Impressum | Nutzungsbedingungen | Datenschutzerklärung
Copyright Stefan Deiters und/oder Lieferanten 1999-2013. Alle Rechte vorbehalten.  W3C