Suche zweier Primzahlen mit bestimmten, übereinstimmenden Ziffern



  • Hallo

    Ich habe vor, mich in der Programmierung zu versuchen, um ein Problem zu lösen.
    Da ich noch kaum Kenntnisse habe, hoffe ich hier auf ein paar gute Tipps.

    Anliegen:

    Es werden zwei Primzahlen gesucht, die eine bestimmte Länge haben und sich in einigen Stellen identisch sind.

    Ich habe nun gedacht, dass ich zunächst die Primzahlen bestimmen müsste, in diesem Fall bis zu einer Länge von genau 11 Stellen.
    Anschließend würde ich die Zahlen untereinander vergleichen wollen.

    Nun meine Fragen:

    Angenommen die Zahl abcd soll gesucht werden und eine weitere Zahl aebf existiert ebenfalls, wobei identische Buchstaben für gleiche Ziffern stehen, welche Möglichkeiten gibt es? Es sind nur einige Ziffern identisch und die Stellen nicht die gleichen.

    Sollte ich dabei alle Primzahlen zunächst in ein Array packen und die einzelnen Felder vergleichen?
    Wie kann ich jedoch die Positionen der Ziffern der einzelnen Zahl mit denen der anderen Zahl abgleichen? Ich will ja schließlich nur eine Ausgabe der Zahlen, die in den Ziffern übereinstimmen und nicht für identische Zahlen.

    Zum anderen frage ich mich, wie verhindere ich, dass sofort nach dem ersten Fund ein Abbruch stattfindet, obwohl es eventuell mehrere Ergebnisse gibt?

    Ich würde mich sehr über einige Anregungen und Lösungsansätze freuen!

    Vielen Dank im Voraus!

    PS: Macht es Sinn die Ergebnisse zunächst in z. B. einer Textdatei abzulegen und anschließend ein anderes Programm darauf anzusetzen?


  • Mod

    Stelle zunächst einmal fest, dass ein klassischer Primzahlsiebalgorithmus für Zahlen bis 10^11 ungefähr 12 GB Speicher braucht. Sofern dein Rechner das packt, ist das eine gangbare Lösung, so etwas zu benutzen. Ansonsten musst du andere Verfahren benutzen, zwischenspeichern, oder clever: Eine Liste runterladen.

    Der Rest ist doch dann bloß ganz normale Kontrollstrukturen. Ich verstehe nicht, was du da für Probleme hast. Du gehst deine Primzahlen durch. Die, auf die dein Kriterium zutrifft gibst du aus, die anderen eben nicht. Wie du die X'te Dezimalziffer einer Zahl bestimmst ist dir bekannt?
    http://de.wikipedia.org/wiki/Stellenwertsystem
    (ich bin immer wieder erstaunt, wie vielen Leuten nicht klar ist, wie Ziffernsysteme funktionieren)



  • Hallo

    Schon mal danke für den Überblick. 🙂 Das Prinzip, denke ich, ist mit schon klar. Allerdings gibt es ja für viele Problemstellungen immer mehrere Wege. Und da ich mit Algorithmen nicht so viele Erfahrungen habe, frage ich hier halt nach. An eine Liste habe ich auch schon gedacht. Das mit dem Speicher war auch ein Grund, weshalb ich nicht einfach drauf los rechnen lassen wollte. Also empfiehlt sich eine modulo-Operation?!

    Sicher gibt es genügend Leute, die viele Vorgehensweisen für Standardfragen aus dem Stehgreif beherrschen und oft anwenden. Ich bin da leider eher Gelegenheitsanwender.
    Meine Frage zielte ja auch nicht ausschließlich auf das alleinige Stellenabgleichen, sondern auf ein sinnvolles und mit einfachen Rechnern zu erledigendes Konzept! 😉


  • Mod

    Irgendwie ist mir unklar, wo deine Schwierigkeiten liegen. Deine Frage klingt fast so, als könntest du keine Schleifen, Verzweigungen oder sonstigen Kontrollstrukturen selbstständig verwenden. Was Voraussetzung ist, um überhaupt Programme schreiben zu können.

    Wo liegt denn bei dir die Schwierigkeit, die Liste der Primzahlen (woher auch immer) durchzugehen und dein Kriterium darauf anzuwenden? Das ist doch ganz elementar, da brauchst du keine ausgefallenen Algorithmen für.



  • Moin

    Vielleicht ist es ja gerade so trivial und auch der beste Weg.
    Ich dachte nur, dass es eventuell irgendwelche Vorgehensweisen gibt, von denen ich noch nie etwas gelesen habe.
    Und das Abgleichen jeder einzelnen Ziffer und der Abgleich über derart viele Zahlenpartner scheint recht üppig zu werden.

    Ja, dafür wurden Rechner erfunden - darüber bin ich auch froh! 😉

    Die Performance bei der Datenmenge einzuschätzen ist nichts mit dem ich bislang konfrontiert war. Dann werde ich das Gerät wohl etwas ackern lassen müssen...

    Ich will hier ja auch niemanden weiter mit dieser Banalität belästigen! 😃


  • Mod

    Bis 10^11 gibt es ungefähr 4 Milliarden Primzahlen. Wenn wir mal pro Zahl großzügig ein paar Tausend CPU-Takte für Prüfung und Ausgabe veranschlagen, dann dauert das ein paar tausend Sekunden, also in der Größenordnung Stunden. Schnell genug? Falls nicht, dann kann man da vielleicht noch irgendwas tricksen (mir fällt aber spontan nichts großartiges ein), aber du musst natürlich auch bedenken, dass jede Stunde die du mit der Verbesserung des Algorithmus verbringst, eine Stunde ist, die der naive Algorithmus hätte länger laufen können.

    Der Aufwand zur Beschaffung der Primzahlen (habe dir ja schon ein paar Möglichkeiten genannt) dürfte sich in ähnlichen Maßstäben bewegen. Das bekannte Siebverfahren ist O(n*log(log(n))), skaliert also recht gut. Runterladen von Listen ist O(n), aber mit in der Regel sehr großen Konstanten. Hochgerechnet von meine bisherigen Erfahrungen mit diesen Algorithmen (beziehungsweise einer typischen Internetverbindung) sollten beide auch in der Größenordnung von vielen Minuten bis wenigen Stunden liegen, je nach Hardware.

    Also empfiehlt sich eine modulo-Operation?!

    Häh, was? Willst du etwa für jede Zahl einzeln testen, ob sie keine kleinere Zahl teilbar ist, indem du alle Möglichkeiten ausprobierst? Das wäre ein ganz bescheidener Primzahltest mit ganz mieser Komplexitätsklasse. Würde den Aufwand wohl in den Bereich von Tagen bis Wochen erhöhen. Ein bisschen clever muss man schon sein. Primzahlsuche ist doch nun wirklich ein Problem, zu dem schon tausende Algorithmen existieren und alle sind sie besser als dieser.



  • Das mit den Stunden wäre schon völlig i.O.
    Ich habe bereits ein Programm geschrieben, welches nach dem Sieb-Verfahren Primzahlen bestimmt, das funktioniert ganz gut.

    Damit hätte ich die Primzahlen. Einen Großteil benötige ich glücklicherweise gar nicht.

    Nun suche ich nunmal noch die 11-stelligen Primzahlen, die an bestimmten Stellen identisch sind und sonst ein bestimmtes Muster aufweisen.

    Nun muss ich noch sehen, dass ich bei Übereinstimmung der jeweiligen Stelle, diese ablege und die Stellen überspringe, die nicht identisch sein müssen, aber zusätzlich auf Kriterien prüfe, wenn in der Zahl selbst die Stelle mehrmals vorkommt.
    Dafür muss ich doch jede Stelle durchgehen?!

    Ich komme einer Idee so langsam näher, aber es ist nicht gerade banal - für mich zumindest, noch nicht 😉 .



  • Magst du auch Matlab benutzen? Dann kannst du dich mehr um deine Problemstellung kümmern, als um das schnick schnack drumherum. Zum Beispiel generierst du dir alle dreistelligen Primzahlen mit:

    range = 100:999;
    primes = isprime(range).*range;
    primes(primes==0) = [];
    

    Und die MathWorks Jungs haben hinter isprime bestimmt super duper schnelle Algorithmen implementiert.

    Edit: Hmmm, auf meiner alten Kiste bekomme ich ab sieben Stellen 'Out of memory'. Vielleicht verkraftet deiner mehr. Ansonsten musst du mit Matlab doch wohl inner Schleife durchlaufen und einzeln mit isprime testen.


Log in to reply