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

Ähnliche Artikel

Kommentar verfassen