Angenommen N = 8. Es gibt 4 Paare (1,8), (2,8), (4,8), (8,8) deren LCM 8 ist. Wenn N = 6. Dann gibt es 5 Paare (1,6), (2,6), (2,3), (3,6), (6,6), deren LCM 6 ist. Jetzt möchte ich wissen, wie man die Anzahl der Paare schnell findet?Von 1 bis N Wie viele Paare haben LCM = N?
Die Frage "Pairs of numbers with at given LCM" bei math.stackexchange.com gibt die Formel
((2e1+1)(2e2+1)...(2ek+1)+1)/2
where e1, e2, ... is the exponents for the unique prime factors of n
für diese Nummer.
dh
8 = 2^3 hat ((2 * 3 + 1) + 1)/2 = 4 solche Paare,
6 = 2^1 * 3^1 hat ((2 * 1 +1) (2 * 1 + 1) +1)/2 = 5 solcher Paare und
60 = 2^2 * 3^1 * 5^1 hat ((2 * 2 + 1) (2 * 1 + 1) (2 * 1 + 1) +1)/2 = 23 solche Paare.
Sie auf eine ähnliche Frage hier beziehen
https://math.stackexchange.com/questions/4152/pairs-of-numbers-with-a-given-lcm
im Grunde, wenn n = (p1^e1) (p2^e2) ... (pk^ek) wobei pi für 1 < Primzahl = i < = k
dann wäre die Lösung ((2e1 + 1) (2e2 + 1) ... (2ek + 1) +1)/2
IHRE SHIFT Taste angeschlagen –