2009-04-22 9 views
0

Ich versuche, einen Algorithmus zu lösen, Project Euler's Problem 200 zu lösen.Benötigen Sie Hilfe beim Lösen des Projekts Euler Problem 200

Wir werden eine sqube definieren eine Anzahl der Form zu sein, p q, wo p und q verschiedenen Primzahlen sind. Beispielsweise 200 = oder 120072949 = 23 .

Die ersten fünf squbes sind 72, 108, 200, 392 und 500.

Interessanterweise 200 ist auch die erste Nummer, für die Sie keine einstelligen ändern kann, um eine Primzahl zu machen; wir werden solche Nummern nennen, prime-proof. Der nächste Primzahl-proof sqube die enthält der zusammenhängende Teilstring "200" 1992008.

200. prime-proof Finden sqube die zusammenhängende Unterkette "200" enthält.

Kann mir bitte jemand in die richtige Richtung zeigen, um mir zu helfen, dieses Problem zu lösen?

+5

Die Leute hier sind nicht freundlich, nur Arbeit für andere zu tun. Wenn Sie einen bestimmten Code haben, der ein anderes Problem hat als "make this work", werden Sie Leute finden, die mehr dazu neigen, Ihnen zu helfen. –

+3

Ich habe mein Bestes getan, um Freddy um eine Frage zu kümmern.Es ist ein interessantes Problem trotz der wirklich faulen Anfangsfrage Formulierung. –

+1

Einverstanden, es ist eine interessante Frage, und eine, die mich daran erinnert, dass Projekt Euler noch am Leben ist, war Alter von, als ich zuletzt besuchte, Ich denke auch, dass, wenn jemand eine Antwort zur Verfügung stellt, BITTE BITTE tun Sie es in psudo-Code , und überlasse die Umsetzung dem Benutzer, zumindest so. Es ist kein kompletter Betrüger. – Fusspawn

Antwort

3

Ich bin mir nicht sicher, dass dies eine große SO Frage ist, aber das sollte Sie zumindest beginnen.

Algorithmisch die brutale Gewalt und Ignoranz Ansatz sollte ziemlich einfach sein:

  1. beginnt mit einem Satz von Primzahlen P
  2. erzeugen „squbes“, indem alle auf der Suche Paare geordnet (P1, P2) mit p1, p2 in P
  3. Bestellen Sie diese Liste, rufen Sie die Menge S (denken Sie: wie können Sie dies tun, während sie erzeugt)
  4. -Test jeweils in S s wiederum sucht Teilzeichenfolge 200
  5. Wenn s enthält " 200 "tes t jede einstellige Modifikation von s, um zu sehen, ob es Prime ist
  6. Wenn keine von ihnen Prime sind, haben Sie eine Prime-Beweis-Sqube gefunden. Setzen Sie es in eine Liste, und wenn Sie den 200. gefunden haben, sind Sie fertig.

Jetzt ist die interessantere Sache hier zu sehen, wenn Sie etwas ein bisschen weniger rohe Kraft und Ignoranz tun können. Erstens, ist das Obige sogar praktisch (unter der Annahme eines schnellen Primalitäts-Tests)? Leicht genug, um abzuschätzen, wie schnell die Squbes wachsen, aber nicht so sehr bei den Prime-Proofs oder bei denen, die 200 enthalten. Kannst du irgendwelche Abkürzungen sehen?

Viel Spaß!

+0

Ich frage mich, ändert sich die erste Ziffer auf 0 erlaubt? –

Verwandte Themen