Ich hatte ein Problem, irgendeine Zahl als Summe von vier Primzahlen auszudrücken.
Bedingungen:
Was ich getan habe:
Mit dem Sieb von Eratosthenes habe ich alle Primzahlen bis zur angegebenen Zahl berechnet.
hat ein Konzept namens Goldbach-Vermutung nachgeschlagen, das eine even Zahl als Summe zweier Primzahlen ausdrückt.
Allerdings stecke ich darüber hinaus fest. Kann mir hier jemand helfen, wie Sie vorgehen könnten?
Das Sieb von Eratosthenes braucht zwei Sekunden, um Primzahlen bis zu 100.000 zu zählen.
Mit der Zeit könnte man immer noch in Ordnung sein. Aufgrund der Goldbach-Vermutung kann jede gerade Zahl größer oder gleich 8 als Summe von 2,2 und zwei weiteren Primzahlen ausgedrückt werden. Jede ungerade Zahl größer oder gleich 9 kann als Summe von 2,3 und zwei weiteren Primzahlen ausgedrückt werden. Es sollte nicht zu lange dauern, um die Primzahlen herauszufinden.
Edit: Eigentlich könntest du das deutlich beschleunigen: Finde für jede gerade Zahl N die größte Primzahl, die kleiner oder gleich N-7 ist, und wähle diese Primzahl und 3, dann suche nach zwei weiteren Primzahlen, die zu deiner Summe passen. Für jede ungerade Zahl N, finde die größte Primzahl größer oder gleich N-6 und wähle sie und zwei, dann wähle wieder zwei Primzahlen.
Sie können den Suchbereich einschränken, indem Sie eine einfache Tatsache notieren: Wenn Sie zwei Zahlen addieren, ist die letzte Ziffer der Summe die letzte Ziffer der Summe der letzten Ziffern der beiden Zahlen. Zum Beispiel 2345 + 24323 = 26668 und 5 + 3 = 8; Wenn die letzten Ziffern eine 2-stellige Zahl ergeben, verwenden Sie die letzte Ziffer, z. 2345 + 5436 = 7781 5 + 6 = 11, deren letzte Ziffer 1 ist.
Nach dem zuvor vorgeschlagenen Algorithmus:
Zum Beispiel
Bei einer Zahl wie 34565 ist die letzte Ziffer 5, die Komponenten kommen aus (0,5), (1,4), (2,3), (3,2), (4,1 ), (5,0), (6,9), (7,8), (8,7), (9,6). Ohne Dubletten bleiben uns (0,5), (1,4), (2,3), (6,9), (7,8). (Berechnen Sie diese für alle letzten Ziffern und Hardcode in Ihr Programm).
Wenn N die ursprüngliche Zahl ist, wählen Sie jede Zahl M aus der "0" Box, prüfen Sie, ob (N-M) ein Mitglied der "5" Box usw. ist, für alle möglichen Kombinationen. Wenn ja, hast du deine Antwort gefunden!
Wenn es nicht die Grenze für die Anzahl Größe (100.000 oder weniger) gab, ist Ihr Problem nicht garantiert, eine Lösung zu haben: siehe schwache Goldbach-Vermutung .
Allerdings ist es wahrscheinlich wahr, zumindest für Zahlen im Bereich der Rechenergebnisse ... sind Sie sicher, dass Ihr Problem darin besteht, keine Zahl die Summe von at meisten vier Primzahlen auszudrücken?
Da 2,3,5,7,11,13,17,19,23 viele Möglichkeiten bieten, würde ich die Zahlen berechnen, die als Summe von drei dieser Zahlen ausgedrückt werden. (zB 2 + 3 + 5 = 10, 2 + 3 + 7 = 2 + 5 + 7 = 12, 3 + 5 + 7 = 15, 2 + 3 + 11 = 16, 2 + 5 + 11 = 18, 3+ 5 + 11 = 19, 2 + 7 + 11 = 20, ... 17 + 19 + 23 = 59.)
Dann nehmen Sie Ihre beliebige Zahl N, finden Sie die nächste Primzahl unterhalb der, die sich von N durch eine der vorberechneten Summen von 3 kleinen Primzahlen unterscheidet. Wenn Sie keine Lösung finden, versuchen Sie es mit der nächsten Primzahl bis N-59. Wenn das immer noch nicht funktioniert, füge andere kleine Primzahlen hinzu.
Verwenden Sie das Wissen über Hauptlücken , um Ihre Lösung zu begrenzen ... die größte Primzahllücke für Primzahlen unter 155921 (größer als 100.000) ist 86.
ps. Ihr Sieb von Eratosthenes sollte keine 2 Sekunden für N = 100.000 nehmen. Sie müssen nur Divisoren bis zur Quadratwurzel von 100.000 = 316 prüfen.
Sobald Sie eine Liste von Primzahlen und eine konkrete Zahl haben, ist das nicht ein Rucksackproblem ?
N ist deine Kapazität und Primzahlen sind deine Gegenstände. Sie haben eine Beschränkung von 4 auf Artikel zählen. Ich würde das mit dynamischer Programmierung lösen, die ziemlich schnell sein sollte.
Hier ist die Empfehlung der Frage, auf die in meinen Kommentaren verwiesen wird:
- Berechne alle Primzahlen mit weniger als N das Sieb von Eratosthenes.
- Tabellieren a Liste der Summen von zwei Primzahlen.
- Sortiere die Liste.
- Überprüfen Sie, ob zwei Nummern vorhanden sind in der Liste die Summe zu N.
- Wenn ja, drucken Sie die entsprechenden vier aus Primzahlen.
Nur zum Thema Sieve, hier ist, was ich für eine nicht optimierte, "dumme" Implementierung halte:
%Vor%Für mich läuft es (mit n = 100000) in einem Bruchteil einer Sekunde.
Es gibt ein ernsthaftes Problem bei der Implementierung des Siebs. Ich habe es einfach in Delphi implementiert, und auf meiner mit 2,93 GHz getakteten Intel Core i7 CPU beträgt die benötigte Zeit weniger als eine Millisekunde (0,37 ms)!
Ich habe den folgenden Code verwendet:
%Vor%