001 – Addition der Vielfachen von 3 oder 5

Wenn wir alle natürlichen Zahlen unter 10, die durch 3 oder 5 teilbar sind, auflisten, erhalten wir:

3, 5, 6, 9

Die Summe daraus ist 23.

Finde die Summe aller Vielfachen von 3 oder 5 unter 1000!

Lösung

Möglichkeit 1

In einer Schleife wird eine Variable bis 999 hochgezählt. Bei jedem Durchlauf wird geprüft, ob der aktuelle Wert durch 3 oder durch 5 geteilt werden kann. Ist dies der Fall, wird der aktuelle Wert auf die Summe addiert:

summe = 0;

for i = 1:999
    if (mod(i, 3) == 0) || (mod(i,5) == 0)
        summe = summe + i;
    end
end

summe

Das Ergebnis ist 233168.

Hätten wir die Zahlen statt bis 1000 bis 100000000 aufaddieren sollen, hätte sich dies in der Rechenzeit bemerkbar gemacht.

Rechenzeit von Möglichkeit 1 für n = 100000000: 13.765252 Sekunden

Möglichkeit 2

Alle Vielfachen von 3 unter 1000 werden summiert. Alle Vielfachen von 5 unter 1000 werden summiert. Die beiden Summen werden addiert. Da die Zahlen, die durch 15 teilbar sind, doppelt gezählt wurden, werden diese wieder abgezogen:

summe = 0;

for i = 3:3:999
    summe = summe + i;
end

for i = 5:5:999
    summe = summe + i;
end

for i = 15:15:999
    summe = summe - i;
end

summe

Rechenzeit von Möglichkeit 2 für n = 100000000: 0.265250 Sekunden

Möglichkeit 3

Die dritte Möglichkeit besteht darin, erst einmal über das Problem nachzudenken, und dann mit dem Programmieren anzufangen. Wir schreiben den Ansatz von Möglichkeit 2 ein wenig um (Grenze 999 wurde zu g verallgemeinert):

x = \sum\limits_{i = 3,i+ = 3}^g i +\sum\limits_{i = 5,i+ = 5}^g i -\sum\limits_{i = 15,i+ = 15}^g i

Wir benutzen nun das Zeichen \div für die ganzzahlige Division:

x = \sum\limits_{i = 1}^{g \div 3} {3i} +\sum\limits_{i = 1}^{g \div 5} {5i} -\sum\limits_{i = 1}^{g \div 15} {15i}

Die Konstanten können wir vor die Summen ziehen:

x = 3\sum\limits_{i = 1}^{g \div 3} i +5\sum\limits_{i = 1}^{g \div 5} i -15\sum\limits_{i = 1}^{g \div 15} i

Nun benutzen wir die Summenformel von Gauß:

\sum\limits_{i = 1}^n i = \frac{{n\left( {n+1} \right)}}<br /> {2}

\Rightarrow \quad x = 3\frac{{\left( {g \div 3} \right)\left( {\left[ {g \div 3} \right]+1} \right)}}<br /> {2}+5\frac{{\left( {g \div 5} \right)\left( {\left[ {g \div 5} \right]+1} \right)}}<br /> {2}-15\frac{{\left( {g \div 15} \right)\left( {\left[ {g \div 15} \right]+1} \right)}}<br /> {2}

Matlab-Code:

g = 999;

summe3 = 3 * 0.5 * floor(g/3) * (floor(g/3) + 1)
summe5 = 5 * 0.5 * floor(g/5) * (floor(g/5) + 1)
summe15 = 15 * 0.5 * floor(g/15) * (floor(g/15) + 1)

summe = summe3 + summe5 - summe15

Rechenzeit von Möglichkeit 3 für n = 100000000: 0.000448 Sekunden

Ähnliche Artikel

Kommentar verfassen