Anzeige
Seite 3 von 7 ErsteErste 12345 ... LetzteLetzte
Ergebnis 21 bis 30 von 63

Thema: Sieb des Eratosthenes

  1. #21
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Anzeige
    Zitat Zitat von Bernhard Beitrag anzeigen
    Über den Daumen gepeilt entspricht das dem Alter des Universums.

    Da muss man also schon wirklich viel Geduld mitbringen .
    Hallo Bernhard,

    es war sogar 150'000x länger als diese 10^17 Sekunden, genau wie Du schreibst das Alter des Universums. Ich habe daraufhin meine Versuche mit dem Backtracking-Algorithmus eingestellt und meine Frage, warum man das Problem Mitte der 1960-iger Jahre nicht mit Computer-Hilfe gelöst hat, war damit auch schon beantwortet.

    Das war damals schon das zweite Mal, dass ich ein Programm geschrieben hatte, dessen Laufdauer länger als das Alter des Universums war; das erste Mal war beim Bestimmen der Untergruppen im Rahmen meiner damaligen Semesterarbeit mit CAYLEY passiert, wo ich die Aufgabe mit purer Rechenleistung erschlagen wollte (natürlich auch sehr zur "Freude" besagten Oberassistenten) und dann eben schliesslich doch die Mathematik bemühen musste. - Wenn ich mich recht entsinne hatte ich es damals mit 28! zu tun.


    Freundliche Grüsse, Ralf

  2. #22
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.179

    Standard

    Hallo zusammen,

    vielleicht erinnert sich noch jemand an diesem Thread, wo ich etwas ähnliches gepostet habe. Falls Bedarf besteht, ich habe den Sourcecode noch.
    101010

  3. #23
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von Kibo Beitrag anzeigen
    vielleicht erinnert sich noch jemand an diesem Thread, wo ich etwas ähnliches gepostet habe.
    Hallo Kibo,

    ist schon ne Weile her, aber ich habe das Thema gerne nochmal gelesen und bin über einen deinen YT-Link (?) weiter auf den folgenden unterhaltsamen Link gestossen: Glitch Primes and Cyclops Numbers - Numberphile (07.12.2015). Interessante Beweisidee (habe es noch nicht komlett nachvolllzogen) am Ende, dass 101 die einzige prime Zyklopen-Binärzahl ist.

    Falls Bedarf besteht, ich habe den Sourcecode noch.
    Ja. Ich würde gerne einen Blick auf den Algorithmus werfen. Hast ja vermutlich auch "gesiebt" und da würde ich gerne mal sehen, wie du es umgesetzt hast.

    Kannst wegen mir gerne auch den "Sieb-Code" hier posten. Dann spart man sich den Download.
    Geändert von Bernhard (11.01.2022 um 08:13 Uhr)
    Freundliche Grüße, B.

  4. #24
    Registriert seit
    07.08.2009
    Ort
    Neubrandenburg, Deutschland
    Beiträge
    2.179

    Standard

    Gerne hier der doch sehr kurze Kern:


    pixelmenge:=10000
    gestrichen:=Object()
    prims:=Object()
    prims.insert(2)
    n=3

    SetTimer render, 200

    Loop 100000
    {
    prim=1
    z=1
    while z<sqrt(n)
    {
    z:=prims[A_Index]
    if not mod(n,z)
    {
    prim=0
    break
    }
    }
    if prim
    prims.insert(n)
    n+=2

    }
    101010

  5. #25
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    OK. Interessant.

    Mit n+=2 werden die geraden Zahlen ausgeschlossen.

    Ist das Visual-Basic?
    Freundliche Grüße, B.

  6. #26
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    Mit n+=2 werden die geraden Zahlen ausgeschlossen.
    Hallo Bernhard,

    Primzahlen grösser gleich 3 sind stets ungerade.

    Man kann die Bestimmung der nächsten Primzahl übrigens weiter optimieren, da Zahlen modulo 5 bis auf die 5 selber keine Primzahlen sind und auch ungerade Vielfache von 3 keine Primzahlen sind:

    2 prim (gesetzt)
    3 prim (Startpunkt)
    5 prim (Startpunkt+2)
    7 prim (+2)
    9 nicht-prim (3+6)
    11 prim (+2)
    13 prim (+2)
    15 nicht-prim (3+2*6 sowie modulo 5)
    17 prim (+2)
    19 prim (+2)
    21 nicht prim (3+3*6)
    23 prim (+2)
    25 nicht-prim (modulo 5)
    27 nicht-prim (3+4*6)
    29 prim
    31 prim
    33 nicht-prim (3+5*6)
    35 nicht-prim (modulo 5)

    u.s.w.

    d.h. wenn man hier etwas clever den nächsten Primzahlkandidaten bestimmt, dann ist 49 (7*7) die erste Nicht-Primzahl, die nicht durch die Kriterien "nicht gerade", "nicht 3+n*6" und "nicht modulo 5" bereits ausgeschlossen wird, die nächste ist dann erst 77 (7*11) und bis 100 gibt es nur noch eine weitere, nämlich 91 (7*13).

    Man hat dann also bis 100 nur drei "Fehlalarme".


    Und eine Addition ist auf jeden Fall schneller als mod(3) und mod(5) zu bestimmen. Allerdings muss man hierfür auch die 5 fix in den Primzahlspeicher setzen, kann also erst bei 5 anfangen, hochzuaddieren.


    Freundliche Grüsse, Ralf
    Geändert von ralfkannenberg (12.01.2022 um 11:36 Uhr)

  7. #27
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    Und eine Addition ist auf jeden Fall schneller als mod(3) und mod(5) zu bestimmen.
    Hallo Ralf,

    wie bereits im ersten Beitrag erwähnt, sehe ich eine Begrenzung nicht bei der Geschwindigkeit, sondern eher beim Speicherbedarf, wenn man möglichst viele Primzahlen berechnen will.

    Deshalb erscheint mir eine Vorauswahl an möglichen Zahlen eher als sinnvoll. Mit der vorgeschlagenen Möglichkeit im ersten Beitrag kann man die höchste berechenbare Primzahl allerdings von <1e9 schätzungsweise auch nur auf <1e11 oder <1e12 heben, womit man dann die Kapazität des Rechners insgesamt wohl auch schon optimal nutzt.
    Freundliche Grüße, B.

  8. #28
    Registriert seit
    16.09.2005
    Beiträge
    8.733

    Standard

    Zitat Zitat von Bernhard Beitrag anzeigen
    sehe ich eine Begrenzung nicht bei der Geschwindigkeit, sondern eher beim Speicherbedarf, wenn man möglichst viele Primzahlen berechnen will.

    Deshalb erscheint mir eine Vorauswahl an möglichen Zahlen eher als sinnvoll. Mit der vorgeschlagenen Möglichkeit im ersten Beitrag kann man die höchste berechenbare Primzahl allerdings von <1e9 schätzungsweise auch nur auf <1e11 oder <1e12 heben, womit man dann die Kapazität des Rechners insgesamt wohl auch schon optimal nutzt.
    Hallo Bernhard,

    das ist wohl alles richtig, wobei ich das sehr schlecht beurteilen kann, weil ich beruflich weder mit rechenintensiven noch mit speicherintensiven Aufgabenstellungen zu tun habe; was ich allerdings nicht ganz verstehe ist, warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.

    Und um Missverständnissen vorzubeugen: als Mathematiker rede ich von exakten Primzahlprüfungen, d.h. nicht von solchen, die eine hohe Wahrscheinlichkeit aufweisen und für Verschlüsselungen und Hacker völlig genügend sind.


    Freundliche Grüsse, Ralf

  9. #29
    Registriert seit
    12.11.2005
    Beiträge
    5.488

    Standard

    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    was ich allerdings nicht ganz verstehe ist, warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen
    Hallo Ralf,

    mich interessieren die exakten Werte der Primzahlfunktion und da ist es naheliegend die leicht zugänglichen Werte über das Sieb dE zu berechnen. Zudem ist das eine nette und vergleichsweise sehr leicht zu lösende Programmieraufgabe. Man hat also schnell ein Erfolgserlebnis.

    statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.
    Ich kenne Online-Listen nur bis 1e6. Das Sieb liefert die exakten Zahlen mit sehr geringem Aufwand bis 1e9.
    Freundliche Grüße, B.

  10. #30
    Registriert seit
    18.04.2016
    Ort
    Dresden
    Beiträge
    481

    Standard

    Anzeige
    Zitat Zitat von ralfkannenberg Beitrag anzeigen
    ... warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.
    Hallo Ralf,

    ich vermute, dass es ähnliche Gründe sind, weshalb immer mehr Nachkommastellen von Pi berechnet werden.

    Gruß, Astrofreund
    "Der Krieg ist gewonnen - aber nicht der Friede."
    Albert Einstein Botschaft an die Nobel-Gedenkfeier in New York, 19. Dezember 1945

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