Kleinste Zahl, die durch alle Zahlen von 1 bis 20 teilbar ist?

Die kleinste Zahl, die durch zwei Zahlen teilbar ist, ist das LCM dieser beiden Zahlen. Tatsächlich ist die kleinste Zahl, die durch eine Menge von N Zahlen x1..xN teilbar ist, die LCM dieser Zahlen. Es ist einfach, das LCM von zwei Zahlen zu berechnen (siehe den Wikipedia-Artikel), und Sie können auf N Zahlen erweitern, indem Sie die Tatsache ausnutzen, dass

Hinweis: Achten Sie auf Überläufe.

Code (in Python):

Rechne alle Ganzzahlen von 1 bis 20 in ihre Primfaktorzerlegungen ein. Zum Beispiel: Faktor 18 als 18 = 3 ^ 2 * 2. Nun finden Sie für jede Primzahl p , die in der Primfaktorzerlegung einer ganzen Zahl im Bereich 1 bis 20 vorkommt, den maximalen Exponenten, den sie unter all diesen Primzahlen hat Faktorisierungen. Zum Beispiel wird die Primzahl 3 den Exponenten 2 haben, weil sie in der Faktorisierung von 18 als 3 ^ 2 erscheint und wenn sie in jeder Primfaktorzerlegung mit einem Exponenten von 3 (dh 3 ^ 3) erscheinen würde muss mindestens so groß sein wie 3 ^ 3 = 27 was außerhalb des Bereichs von 1 bis 20 liegt. Nun sammle alle diese Primzahlen mit ihrem entsprechenden Exponenten und du hast die Antwort.

Finden wir als Beispiel die kleinste Zahl, die durch alle Zahlen von 1 bis 4 teilbar ist.

Die angezeigten Primzahlen sind 2 und 3 . Wir stellen fest, dass der maximale Exponent von 2 2 und der maximale Exponent von 3 1 ist. Die kleinste Zahl, die durch alle Zahlen von 1 bis 4 teilbar ist, ist also 2 ^ 2 * 3 = 12.

Hier ist eine relativ einfache Implementierung.

Beispielausgabe:

Siehe Ссылка Mit zwei Zahlen a und b können Sie gcd (a, b) berechnen und die kleinste Zahl, die durch beide teilbar ist, ist a * b / gcd (a, b). Die naheliegendste Sache ist dann, eine Art Laufsumme davon zu halten und die Zahlen, die Sie interessieren, eins nach dem anderen hinzuzufügen: Sie haben eine Antwort bis jetzt A und fügen die nächste Zahl X_i hinzu, indem Sie

A '= A * X_i / (gcd (A, X_i))

Sie können sehen, dass dies tatsächlich funktioniert, indem Sie überlegen, was Sie bekommen, wenn Sie alles faktorisieren und als Produkte von Primzahlen ausschreiben. Dies sollte Ihnen erlauben, die Antwort von Hand auszuarbeiten.

Hinweis:

statt die Zahl um 1 zu erhöhen, können Sie sie um 20 erhöhen (wird viel schneller arbeiten). Natürlich kann es auch andere Verbesserungen geben, wenn ich später Zeit habe, denke ich darüber nach. Hoffe ich habe dir ein bisschen geholfen.

Die betreffende Zahl ist das kleinste gemeinsame Vielfache der Zahlen 1 bis 20.

Weil ich faul bin, lass ** Exponentiation darstellen. Sei kapow (x, y) der ganzzahlige Teil des Logs zur Basis x von y. (Zum Beispiel, Kapow (2,8) = 3, Kapow (2,9) = 3, Kapow (3,9) = 2.

Die Primzahlen kleiner oder gleich 20 sind 2, 3, 5, 7, 11, 13 und 17. Das LCM ist

Weil sqrt (20) & lt; 5, wir wissen, dass Kapow (i, 20) für i & gt; = 5 ist 1. Durch Inspektion ist das LCM

  

LCM = 2 Kapow (2,20) * 3 Kapow (3,20)   * 5 * 7 * 11 * 13 * 17 * 19

was ist

  

LCM = 2 4 * 3 2 * 5 * 7 * 11 * 13 *   17 * 19

oder

  

LCM = 16 * 9 * 5 * 7 * 11 * 13 * 17 *   19

Der Vektor wird zum Speichern der Faktoren der kleinsten Zahl verwendet.

Dies kann Ihnen helfen Ссылка

Die Primfaktorzerlegung von 232.792.560

2 ^ 4 • 3 ^ 2 • 5 • 7 • 11 • 13 • 17 • 19

Ruby Cheat:

dies ist in c

}

Hier ist eine C # -Version von @ MAKs Antwort, vielleicht gibt es List reduce in C #, ich habe etwas online gefunden, aber keine schnellen Beispiele, also habe ich einfach eine for-Schleife anstelle von reduce :

Wenn Sie das Maximum n angeben, möchten Sie die kleinste um 1 bis 20 teilbare Zahl zurückgeben.

Schauen wir uns die Menge von 1 bis 20 an. Zunächst enthält sie eine Anzahl von Primzahlen, nämlich:

Also, weil es mit 19 teilbar sein muss, können Sie nur Vielfache von 19 überprüfen, weil 19 eine Primzahl ist. Danach prüfen Sie, ob es durch das darunter liegende geteilt werden kann usw. Wenn die Zahl durch alle Primzahlen erfolgreich geteilt werden kann, kann sie durch die Zahlen 1 bis 20 geteilt werden.