Anzeige
Seite 4 von 7 ErsteErste ... 23456 ... LetzteLetzte
Ergebnis 31 bis 40 von 64

Thema: Sieb des Eratosthenes

  1. #31
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.179

    Standard

    Anzeige
    Zitat Zitat von Bernhard Beitrag anzeigen
    ...

    Ist das Visual-Basic?

    Das ist in Autohotkey geschrieben, eine sehr bequeme Interpretersprache die z.B. auch opengl kann
    101010

  2. #32
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Daumen hoch

    Zitat Zitat von Kibo Beitrag anzeigen
    Das ist in Autohotkey geschrieben
    OK. Der Code sieht tatsächlich recht übersichtlich aus.
    Freundliche Grüße, B.

  3. #33
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.179

    Standard

    Ich hab dir den gesamten Sourcecode auf mein Onedrive hochgeladen. Benötigt werden primpixel 4.ahk, GLini.ahk und gl.ahk. Die kompilierten exes von 2015 liegen da auch noch. Das waren noch Zeiten...

    https://1drv.ms/u/s!AmLG71NEfTlYhwYy...v4K8E?e=UclLkG
    Geändert von Kibo (14.01.2022 um 08:23 Uhr)
    101010

  4. #34
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von Kibo Beitrag anzeigen
    Ich hab dir den gesamten Sourcecode auf mein Onedrive hochgeladen. Benötigt werden primpixel 4.ahk, GLini.ahk und gl.ahk. Die kompilierten exes von 2015 liegen da auch noch.
    Prima. Tut. Danke
    Das waren noch Zeiten...
    Ist ne Weile her, ja . "Damals" gab es noch kein SpaceX-Starship zum ansehen
    Geändert von Bernhard (14.01.2022 um 12:31 Uhr)
    Freundliche Grüße, B.

  5. #35
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    mich interessieren die exakten Werte der Primzahlfunktion
    Nach einiger Suche im www möchte dazu diese Seite https://en.wikipedia.org/wiki/Meisse...hmer_algorithm und insbesondere die zugehörige Referenz 1 empfehlen.

    Das zugehörige pdf ist auch auf der deutschen Seite zu https://de.wikipedia.org/wiki/Ernst_Meissel verlinkt.

    Nebenbei: Lesenswert finde ich auch: https://de.wikipedia.org/wiki/Waringsches_Problem
    Freundliche Grüße, B.

  6. #36
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Hier: https://codegolf.stackexchange.com/q...primes-up-to-n findet man Implementierungen des Siebs in weiteren Programmiersprachen, innerhalb eines Wettbewerbs zum schnellsten Berechnen einiger Werte der Primzahlfunktion bis 2e9. Der erste Beitrag verwendet dabei die Formeln von Referenz 2 des vorher angegebenen Links zum Meissel-Lehmer-Algorithmus.

    Auch interessant und unterhaltsam: Mathe RÄTSEL Primzahlen – Knifflige Rätsel
    Freundliche Grüße, B.

  7. #37
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Da die Programmierung des Siebs nicht gerade viel Diskussionsstoff liefert, erweitere ich das Thema auf die exakte Berechnung der Primzahlfunktion. Zwei Referenzen sind dafür bereits über die Seite: https://en.wikipedia.org/wiki/Meisse...hmer_algorithm frei verfügbar.

    Meine Erfahrungen mit der Programmierung der dort vorgestellten Verfahren möchte ich hiermit gerne zur Diskussion und zur Verwendung stellen:

    a) Das "Sieb" liefert mit einem handelsüblichen Büro-PC relativ leicht und in überschaubarer Zeit alle Primzahlen < 1e9. Begrenzender Faktor ist dort eher der Speicher, da man mit einer wenig aufwändigen Programmierung ca. 0.5e9 Bits für das Sieb vorhalten muss. Daraus ergibt sich überschlägig eine Speicherbelegung von 1e9 Byte, was ungefähr 1 GB RAM entspricht.

    b) Mit dem Meissel-Lehmer-Algorithmus kann man mit diesem Sieb dann zB den maximalen Wert von pi(1e13) berechnen, wobei dann die Rechenzeit schon mehrere Minuten betragen kann. Bei meiner Implementierung liege ich aktuell für diesen Wert bei ca. 20 Minuten Rechenzeit. Der korrekte Wert für pi(1e13) kann mit den Werten dieser Seite https://de.wikipedia.org/wiki/Primza...ahlenbeispiele kontrolliert werden.

    Für größere Werte für pi(x) wird bei Verwendung des normalen Meissel-Lehmer-Algorithmus von 1958 vor allem die Rechenzeit problematisch. Durch eine rekursive Anwendung des Gesamtalgorithmus für pi(x) scheint der Wert für pi(1e14) auch noch berechenbar zu sein, allerdings habe ich die Programmausführung nach einer Stunde Rechenzeit dann abgebrochen.

    Problematisch bezüglich der Rechenzeit ist ab pi(1e13) nur die (rekursive) Berechnung der Funktion phi(x,a). Für diese Berechnung findet man in der Veröffentlichung des erweiterten Meissel-Lehmer-Algorithmus eine neue Abbruchbedingungen, welche die Laufzeit reduzieren sollte.
    Geändert von Bernhard (31.01.2022 um 23:26 Uhr)
    Freundliche Grüße, B.

  8. #38
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Per Suchmaschine findet man schnell interessante Treffer zum erweiterten Meissel-Lehmer-Algorithmus, wie zB eine Implementierung in C: https://github.com/jfkingiii/meissel-lehmer .

    Ich habe den zentralen Quelltext von hier: https://github.com/jfkingiii/meissel...type/ML_test.c mal für MS-Visual Studio C++ angepasst und damit dann pi(1e13) berechnen lassen.

    Das korrekte Ergebnis war dann auch nach ca. 1-2 Minuten Rechenzeit zu sehen, was eine beeindruckende Verkürzung der Rechenzeit im Vergleich zum normalen Meissel-Lehmer-Verfahren zeigt.

    Bei der Berechnung von pi(1e14) ergeben sich dann neue Probleme bei der Speicherbelegung.
    Freundliche Grüße, B.

  9. #39
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Freundliche Grüße, B.

  10. #40
    Registriert seit
    16.03.2022
    Beiträge
    14

    Standard

    Anzeige
    Hallo Bernhard,

    Das was du im Startbeitrag geschrieben hast, hatte ich mir auch schonmal überlegt. Ich hab dann aber festgestellt, dass es nach der 3 dann nicht mehr viel bringt. Im Prinzip reduziert man ja die Größe mit jeder Primzahl p auf (p-1)/p. Also 1/2, 2/3, 4/5, 6/7, 10/11,... und sobald das Primzalprodukt größer n ist, ist dann ja auch schon Schluss. Das erreicht man ja auch relativ schnell.

    Ich hatte das mal so implementiert, dass ich immer Kopien erstellt habe und vielfache des Primzahlprodukts draufaddiert habe. Also Angefangen mit

    [1, 5]

    Fünf "Kopien" (bzw. ein Orginal und 4 "Kopien"):

    [1, 5, 7, 11, 13, 17, 19, 23, 25, 29]

    5 und 25 werden rausgestrichen, da sie durch 5 teilbar sind. Dann 7 "Kopien" (bzw. ein Orginal und 6 "Kopien").

    [1, 7, 11, 13, 17, 19, 23, 29, 31, 37,...,199, 203, 209]

    Alle durch 7 Teilbaren rausstreichen usw.

    Dabei muss vorher immer noch überprüft werden, ob das Primzalprodukt n übersteigt. Wenn das der Fall ist, machst du entsprechend weniger Kopien und die letzte Kopie sollte dann auch schon früher abgeschnitten werden.

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