Alle Herausforderungen
Schwierig 0 gelöst 0% Erfolgsquote

Nicht abundante Summen

Addiere alle Zahlen bis zu einer Grenze, die sich nicht als Summe zweier abundanter Zahlen schreiben lassen.

Das lernst du

  • Teilersummen für einen ganzen Bereich mit einem Sieb berechnen
  • Erreichbare Summen in einem booleschen Array markieren
  • Eine doppelte Schleife abbrechen, sobald die Summen die Grenze überschreiten

Problem

Eine Zahl heißt abundant, wenn die Summe ihrer echten Teiler (aller Teiler außer ihr selbst) größer ist als die Zahl. Die kleinste ist 12: 1 + 2 + 3 + 4 + 6 = 16. Manche Zahlen lassen sich als Summe zweier abundanter Zahlen schreiben (dieselbe Zahl darf zweimal vorkommen, wie bei 24 = 12 + 12), andere nicht. Addiere alle positiven ganzen Zahlen von 1 bis limit, bei denen das nicht geht.

Implementiere non_abundant_sums(limit).

Bestimme die Teilersummen aller Zahlen auf einmal mit einem Sieb, sammle die abundanten Zahlen und markiere dann jede Paarsumme, die innerhalb der Grenze bleibt.

Eingabe

limit: Die größte zu prüfende Zahl.

Ausgabe

Gib die Summe aller n mit 1 ≤ n ≤ limit zurück, die keine Summe zweier abundanter Zahlen sind.

Einschränkungen

1 ≤ limit ≤ 10.000

Beispiele

Beispiel 1
Eingabe:
limit = 23

Erwartete Ausgabe:
expected = 276
Eingabe:
long long limit = 23;

Erwartete Ausgabe:
long long expected = 276;
Eingabe:
long limit = 23;

Erwartete Ausgabe:
long expected = 276;

Erläuterung

Keine zwei abundanten Zahlen ergeben zusammen 23 oder weniger, also zählt jede Zahl: 1 + 2 + ... + 23 = 276.

Beispiel 2
Eingabe:
limit = 30

Erwartete Ausgabe:
expected = 411
Eingabe:
long long limit = 30;

Erwartete Ausgabe:
long long expected = 411;
Eingabe:
long limit = 30;

Erwartete Ausgabe:
long expected = 411;

Erläuterung

24 = 12 + 12 und 30 = 12 + 18 fallen weg, also lautet die Antwort 465 − 24 − 30 = 411.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Addiere für jedes i die Zahl i zur Teilersumme von 2i, 3i, 4i, ...

Hinweis 2

Sammle die abundanten Zahlen in aufsteigender Reihenfolge.

Hinweis 3

Brich für jedes Paar a ≤ b die innere Schleife ab, sobald a + b die Grenze überschreitet.

Erwartete Komplexität

Zeit O(limit log limit + A²) bei A abundanten Zahlen, zusätzlicher Speicher O(limit)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.