005 – Kleinstes gemeinsames Vielfaches der Zahlen 1 bis 20

2520 ist das kleinste gemeinsame Vielfache der Zahlen 1 bis 10.

Was ist das kleinste gemeinsame Vielfache der Zahlen 1 bis 20?

Lösung

Möglichkeit 1

Um das kleinste gemeinsame Vielfache der Zahl x zu bestimmen, führen wir für jeden Teiler t eine Primfaktorzerlegung durch. Dabei wird die Anzahl n_i der vorkommenden Primfaktoren p_i bestimmt. Für jede Primzahl p_i wird ihr häufigstes Vorkommen n_{i,\max} gespeichert. Das kleinste gemeinsame Vielfache kgv ist dann:

kgv = \prod\limits_i {\left\{ {p_i^{{n_{i,\max }}}} \right\}}

In Matlab wird dies durch drei Schleifen realisiert. Die erste Schleife stellt den Vektor mit Primzahlen auf, die zweite führt die Primfaktorzerlegung durch und die dritte berechnet das kleinsge gemeinsame Vielfache:

grenze = 20;
primVec = 2;

for prim = 3 : grenze
    wurzel = floor(sqrt(prim));
    istPrim = 1;
    if mod(prim, 2) == 0
        istPrim = 0;
    end
    for teiler = 3 : 2 : wurzel
        if mod(prim, teiler) == 0
            istPrim = 0;
        end
    end
    if istPrim == 1
        primVec = [primVec prim];
    end
end

primVec
primMax = zeros(1, length(primVec));

for teiler = 2 : grenze
    primAct = zeros(length(primVec));
	for primNummer = 1 : length(primVec)
        while mod(teiler, primVec(primNummer)) == 0
            teiler = teiler / primVec(primNummer);
            primAct(primNummer) = primAct(primNummer) + 1;
        end
    end
    for primNummer = 1 : length(primVec)
        if primMax(primNummer) < primAct(primNummer)
            primMax(primNummer) = primAct(primNummer);
        end
    end
end

primMax
kgv = 1;

for primNummer = 1 : length(primVec)
    for primAnzahl = 1 : primMax(primNummer)
        kgv = kgv * primVec(primNummer);
    end
end

kgv

Ergebnis: 232792560
Rechenzeit: 0.000313 Sekunden

Möglichkeit 2

Der oben beschriebene Ansatz funktioniert schon sehr gut, er kann aber optimiert werden.

Der erstellte Vektor mit Primzahlen lautet:

2 3 5 7 11 13 17 19

Die jeweiligen Exponenten sind:

4 2 1 1 1 1 1 1

Wir suchen nun nach einer Berechnungsvorschrift für die Exponenten, die es uns erspart, die Primfaktorzerlegung durchzuführen.

Als erstes betrachten wir den Primfaktor 2. Es gilt:

{2^2} = 4 < 20,\quad {2^3} = 8 < 20,\quad {2^4} = 16 < 20,\quad {2^5} = 32 > 20

16 ist die größte Zweierpotenz im Intervall [1,20]. Der Exponent für 2 muss also 4 sein. Analog gilt für den Primfaktor 3:

{3^2} = 9 < 20,\quad {3^3} = 27 > 20

Der Exponent für 3 ist daher 2. Als Gleichung aufgeschrieben:

p_i^{{n_{i,\max }}} = x

Wir lösen nach dem gesuchten Exponenten auf:

{n_{i,\max }}\log \left( {{p_i}} \right) = \log \left( x \right)\quad  \Rightarrow \quad {n_{i,\max }} = \frac{{\log \left( x \right)}} {{\log \left( {{p_i}} \right)}}

Da die Koeffizienten n_{i,\max } natürliche Zahlen sein müssen, runden wir nach unten ab:

{n_{i,\max }} = \left\lfloor {\frac{{\log \left( x \right)}} {{\log \left( {{p_i}} \right)}}} \right\rfloor

Beispiel:

x = 20,\quad {p_1} = 2\quad  \Rightarrow \quad {n_{1,\max }} = \left\lfloor {\frac{{\log \left( {20} \right)}} {{\log \left( {18} \right)}}} \right\rfloor  = \left\lfloor {4,32} \right\rfloor  = 4

Um das Verfahren noch weiter zu optimieren, nutzen wir die Information, dass

{n_{1,\max }} = 1\quad \forall {p_i} > \sqrt x

Dies setzen wir nun alles in Matlab um:

grenze = 20;
primVec = 2;

for prim = 3 : grenze
    wurzel = floor(sqrt(prim));
    istPrim = 1;
    if mod(prim, 2) == 0
        istPrim = 0;
    end
    for teiler = 3 : 2 : wurzel
        if mod(prim, teiler) == 0
            istPrim = 0;
        end
    end
    if istPrim == 1
        primVec = [primVec prim];
    end
end
primVec

primMax = ones(1, length(primVec));
kgv = 1;
it = 1;
while primVec(it) < sqrt(grenze)
    primMax(it) = floor(log(grenze) / log(primVec(it)));
    it = it + 1;
end
primMax

for it = 1 : length(primMax)
    kgv = kgv * primVec(it) ^ primMax(it);
end

kgv

Rechenzeit: 0.000262 Sekunden

This Post Has One Comment

  1. Wenn man bereits weiß, daß 2.520 die kleinste Zahl ist, die alle Zahlen 1, 2, …, 10 als Faktoren enthält, daß die dort bereits enthaltenen Primzahlen 2, 3, 5 und 7 sind, von denen bereits die 3. Potenz von 2 und die 2. Potenz von 3 in 2.520 enthalten ist, daß es in 11, 12, …, 20 nur mit 16 (= 2 hoch 4) eine höhere Zweierpotenz, aber keine höhere
    Dreier-, Fünfer- oder gar Siebenerpotenz gibt und in 11, 12, …, 20 als weitere Primzahlen nur 11, 13, 17 und 19
    enthalten sind, dann ist die gesuchte Zahl 2.520 * 2 * 11 * 13 * 17 * 19 = 232.792.560, was sich mit jedem Taschenrechner ohne irgendwelches Programmieren leicht verifizieren läßt.

Leave a Reply

Close Menu