Dann gehe durch jede Zahl von 10.000 bis 2. Prüfe für jede von diesen, ob die Primfaktorzerlegung der Zahl eine Teilmenge der gegebenen Liste ist. Wenn es so ist, haben wir die Antwort gefunden.
Partition1 ist der Hauptfaktor der Zahl. Partition2 ist einfach primeNumbers - Partition1 .
Hier ist der psuedocode:
%Vor%Ich nehme an, das sind Hausaufgaben. Die Antwort ist 2 * 4999 (9998), durch Inspektion.
Die Brute-Force-Technik ist (sollte) offensichtlich. Nimm eine Liste aller Primzahlen x, so dass 0 & lt; = x & lt; = 5000 (da du hier nach Faktoren suchst, wirst du Zahlen multiplizieren ... und da die kleinste Primzahl 2 ist, brauchst du nicht sich um etwas zu kümmern, das größer als 5000 ist). für jedes Element x in der Liste, iterieren Sie über die Liste erneut jedes y in der Liste zu prüfen. Multiplizieren Sie sie zusammen und notieren Sie das Delta zwischen dem Produkt und 10000. Halten Sie das kleinste.
Eine andere Möglichkeit wäre, mit 10000 zu beginnen und seine Primfaktoren (falls vorhanden) zu berechnen.
Zum Beispiel:
%Vor%Klingt nach einer Neuformulierung des Rucksackproblems . Während Ihr multiplikativ ist, berechnet man den Logarithmus der Primzahlen und die Zielzahl verwandelt es in ein additives Problem.
Aber selbst wenn das allgemeine Knapsack-Problem schwer ist, könnte Ihre bestimmte Teilmenge von Problemen eine schnelle Lösung haben.
Seit 2^14 = 16384 können Sie höchstens 13 Primfaktoren haben, von denen höchstens 5 verschieden sein können (weil 2*3*5*7*11*13 = 30030 > 10000 ). Die einfachste Lösung besteht darin, über alle Kombinationen zu iterieren. Wenn Sie möchten, dass eines der Produkte 10.000 am nächsten kommt, dann gehen Sie alles durch. Wenn Sie nur eine Version wünschen, in der das Produkt beider Partitionen kleiner als 10.000 ist, können Sie stoppen, sobald Sie eine Lösung haben. Selbst ohne Optimierung wird das bei heutigen Maschinen nur einen Bruchteil einer Sekunde dauern.