Hilfe mit Projekt Euler # 200?

Mögliche Duplizieren:
Need help solving Project Euler problem 200 Hilfe mit Projekt Euler # 200?

Ich schrieb eine Brute-Force-Lösung in Java auf, die mehrere Stunden laufen dauert, und erzeugt die erste 500+ Sqube-Nummern, von denen ich dachte, dass sie ausreichen sollten. Keine der Antworten von 190 bis 210 scheint jedoch die richtige Antwort zu sein.

Ich frage mich, was ich hier falsch mache und wie ich das optimieren könnte. Könnte das Problem in BigInteger.isProbablePrime() liegen?

Ich bin mir nicht sicher, ob Stackoverflow der beste Platz ist, um das zu fragen, aber ich bin festgefahren. Ich habe meinen Code und die generierten Daten eingefügt.

Ich würde es wirklich schätzen, wenn jemand mir einige Hinweise oder Hinweise geben würde.

Edit: Ich habe das Programm wieder einfach mit den ersten 500.000 Primzahlen ausgeführt; brauchte einen Tag um zu laufen, produzierte aber die richtige Antwort.

Quelle

2009-06-18 Lucky

Wissen Sie, ich dachte gerade neulich, dass es Wochen her ist, seit wir eine Euler-Frage gesehen haben. Und jetzt taucht einer auf. Gespenstisch...Und wenn es ein genaues Duplikat von "dieser Frage" ist, warum hast du es dann erneut gepostet? Suchst du nur nach einem Kampf? :-) – paxdiablo

Nicht genau. Der andere ist Monate alt und scheint eine andere Absicht zu haben. – Lucky

Dann warst du sehr dumm zu sagen, dass es ein genaues Duplikat war. Ich schlage vor, dass Sie das ändern. – paxdiablo

Ich bin ein Projekt Euler Administrator. Bitte poste keine Informationen, die das Problem für andere verderben könnten, insbesondere Code und Antworten, sogar halb funktionierenden Code. Bitte bearbeiten Sie Ihre Frage entsprechend. EDIT: Vielen Dank dafür!

Es ist nicht ungewöhnlich, dass Solver das Web verwenden, um nach Informationen zur Lösung eines Problems zu suchen, und es würde etwas Spaß machen, wenn sie auf einen solchen Spoiler stoßen würden. (Ja, ich weiß, es gibt Websites mit vielen Lösungen fertig, aber zumindest sind sie in der Regel für die niedrigeren nummerierten einfache Probleme.)

Wir haben forums für die Erörterung von Schwierigkeiten mit Problemen und bekommen Hinweise, die aggressiv sind für Spoiler bearbeitet.

Quelle

2009-06-19 18:56:05 xan

BS: Wenn man Antworten nicht verdorben haben will, kann er die Seite umgehen. QED. –

Sie sollten nicht an eine clevere Lösung denken, die nicht einen Tag oder sogar eine Stunde dauert? : D Ich denke, das Problem ist isProbablePrime, die nicht garantiert, dass eine Zahl eine Primzahl ist. Es sagt nur, dass eine Primzahl, die gefunden wurde, eine Primzahl mit einer gewissen Wahrscheinlichkeit sein könnte. Sie sollten einen Algorithmus verwenden, der sicher ist, dass er eine Primzahl gefunden hat.

Quelle

2009-06-19 15:56:38

Der Punkt von isProbablyPrime ist, dass es deutlich schneller ist als a bestimmterer Algorithmus; Außerdem kann das Genauigkeitsniveau so hoch eingestellt werden, dass eine Brute-Force-Berechnung mit größerer Wahrscheinlichkeit einen Fehler aufweist (aufgrund eines Hardwarefehlers). Das ist nicht die Quelle der Langsamkeit. –

Ich meinte nicht, dass dies die Quelle der Langsamkeit ist. Ich meinte damit das Problem wieso es beim ersten mal nicht geklappt hat und dann an einer Wiederholung gearbeitet hat könnte dass er isProbablePrime benutzt –

Die erste Antwort ist falsch, weil isProbablyPrime nicht immer korrekt ist (daher die Wahrscheinlich). Es ist langsam, zum Teil, weil Sie BigInteger verwenden. Alle beteiligten Werte passen lange zusammen. Warum nicht lange benutzen?

Quelle

2009-06-19 18:33:21

Es könnte einige einfache Refactorings geben, die Sie einsparen könnten. Es scheint, dass der Großteil der Zeit in der verschachtelten for-Schleife verbracht wird. Die Größenordnung ist n Quadrat. Sie können die Komplexität reduzieren, indem Sie keine Schleifen verschachteln. Ein weiteres Problem besteht darin, dass Sie mehr potenzielle Ergebnisse als erforderlich finden. Sie müssen nur 200 finden. Der Grund, warum Sie mehr finden müssen, liegt an der Tatsache, dass Sie die möglichen Ergebnisse nicht in ihrer numerischen Reihenfolge finden. Das TreeSet hält die Ergebnisse in der richtigen Reihenfolge, aber der Algorithmus wäre schneller, wenn er beim 200sten Ergebnis stoppen könnte.

Quelle

2009-06-20 00:56:12 Trevor

Hilfe mit Projekt Euler # 200?

Antwort

Verwandte Themen