012 – Dreieckszahlen

 

Eine Dreieckszahl ist eine Zahl, die der Summe aller Zahlen von 1 bis zu einer Obergrenze n entspricht. Beispielsweise ist die 10 eine Dreieckszahl, da 1+2+3+4 = 10 ist. Die ersten Dreieckszahlen sind

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55

Wir schreiben zu den Dreieckszahlen ihre Teiler auf:

1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

Wir sehen, dass 28 die erste Dreieckszahl mit 5 Teilern ist.

Was ist die erste Dreieckszahl mit mehr als 500 Teilern?

Lösung

Die Dreieckszahlen werden in einer Schleife gebildet und ihre Teiler werden gezählt. Dabei wird nur bis zur Wurzel der zu testenden Zahl hochiteriert, da die Anzahl der Teiler dann nur noch verdoppelt werden muss.

grenze = 500;
nummer = 1;
teiler = 1;
zahl = 1;

while teiler < grenze
    teiler = 0;
    nummer = nummer+1;
    zahl = zahl+nummer;
    for i = 1 : floor(sqrt(zahl))
        if mod(zahl, i) == 0
            teiler = teiler+2;
        end
    end
end

zahl

Ergebnis: 76576500
Rechenzeit: 4.217793 Sekunden

Verbesserungen

Der Algorithmus kann verbessert werden, indem für die zu testende Zahl eine Primfaktorzerlegung durchgeführt wird, so dass gilt:

N = {p_1}^{{a_1}} \cdot {p_1}^{{a_1}} \cdot  \ldots  \cdot {p_n}^{{a_n}}

Die Anzahl der Teiler der Zahl N lässt sich dann berechnen durch

D\left( N \right) = \left( {{a_1}+1} \right) \cdot \left( {{a_2}+1} \right) \cdot  \ldots  \cdot \left( {{a_n}+1} \right)

Dazu muss natürlich noch ein Primzahlvektor erstellt werden, aber dies lässt sich wie in den letzten Aufgaben gezeigt sehr effizient lösen. Der so optimierte Algorithmus läuft in unter 10 Millisekunden!

Ähnliche Artikel

Kommentar verfassen