Bevor Sie beginnen, lassen Sie mich sagen: Es ist keine Hausaufgabe, einfach nur, alt, lustig.
Nun versuche ich, einen Algorithmus zu finden, der diese Frage beantworten kann 1 / x + 1 / y = 1 / n! .
Und wie Sie anhand des obigen Links sehen können, hat der Autor nur nach Hinweisen und nicht nach der tatsächlichen Antwort gefragt, daher bitte ich um dasselbe.
Ich vereinfachte den Ausdruck bis (x - n!) (y - n!) = (n!) ^ 2 wie von vorgeschlagen eine der Antworten , und zu dieser Zeit verstand ich, dass die Anzahl der Kombinationen von (x, y) Paaren die gleiche ist wie die Anzahl der Teiler von n! ^ 2 (korrigiere mich, wenn ich falsch liege) .
Also, wie von der akzeptierten Antwort vorgeschlagen, versuche ich, die Multiplikation aller Faktoren zu erhalten Primes komponieren N! ^ 2.
Ich habe einen Code in C mit Testdivision zur Faktorisierung von N! ^ 2 und dem Sieb von Eratosthenes , um alle Primzahlen auf sqrt (N! ^ 2) zu bringen.
Das Problem ist jetzt Speicher, ich habe mit N = 15 versucht und mein Mac (Quad Core 6GB Speicher) ist fast an mir gestorben. Das Problem war Gedächtnis. Also habe ich ein paar Printf's hinzugefügt und mit N = 11 versucht:
%Vor%Die Liste enthält alle Primfaktoren von N! ^ 2 (neben 1 und N! ^ 2 natürlich).
Ich möchte einige Hinweise zur Minimierung des Speicherverbrauchs und möglicher Optimierungen erhalten.
Code unten, es war nur ein schnelles Experiment, also bin ich sicher, dass es optimiert werden kann.
%Vor%BEARBEITEN:
Als Beispiel werde ich Ihnen die Berechnung zeigen, um alle möglichen positiven ganzzahligen Lösungen auf die Anfangsgleichung zu bekommen:
3! ^ 2 = 36 = (3 ^ 2 * 2 ^ 2 * 1 ^ 0)
Also gibt es (1 + 2) (1 + 2) (1 + 0) = 9 mögliche positive ganzzahlige Lösungen für die diophantische Gleichung. Verdoppeln Sie, wenn Sie negative ganze Zahlen zählen. Ich benutze WolframAlpha , um sicher zu sein.
EDIT 2:
Ich denke, ich habe gerade herausgefunden, "was für ein Faktor ist", ich bekomme diese sehr interessante Ausgabe:
%Vor%Danke: D
Der Trick hier ist, genau zu erkennen, was ein faktorieller N! ist. Es ist ein Produkt aller Zahlen von 1 bis N . Das ist schon ein großer Schritt vorwärts.
Sie müssen also nur jede der Zahlen von 1 auf N faktorisieren.
In diesem Sinne müssen Sie nicht bis N! durchgehen. Ziehe nur bis zu sqrt(N) durch. Und der Rest fasst nur all Ihre Primfaktoren zusammen.
Noch einfacher, Sie müssen die Zahlen nicht auf N hochrechnen. Sie müssen nur Primfaktoren zählen. Und das können Sie tun, ohne sich Gedanken darüber zu machen, welche Zahlen Faktoren sind.
Lass mich 15 mit der Hand machen.
Bis zu 15 gibt es 7 Vielfache von 2, 3 Vielfachen von 4 und 1 Vielfachen von 8, für insgesamt 11 Faktoren von 2.
Bis zu 15 gibt es 5 Vielfache von 3 und ein Vielfaches von 9 für insgesamt 6 Faktoren von 3.
Bis zu 15 gibt es 3 Vielfache von 5, für insgesamt 3 Faktoren von 5.
Bis zu 15 gibt es 2 Vielfache von 7, für insgesamt 2 Faktoren von 7.
Es gibt jeweils 1 Vielfaches von 11 und 13.
Also 15! = 2 11 * 3 6 * 5 3 * 7 2 * 11 * 13.
Um eine Primfaktorzerlegung von N zu finden! Sie müssen:
Tags und Links algorithm c math number-theory prime-factoring