Schwierig 0 gelöst 0% Erfolgsquote

Non-Abundant Sums

Add up the numbers up to a limit that cannot be written as the sum of two abundant numbers.

Das lernst du

  • Compute divisor sums for a range with a sieve
  • Mark reachable sums with a boolean array
  • Cut a double loop short once sums pass the limit

Problem

Übersetzung anzeigen

A number is abundant when its proper divisors (all divisors except itself) add up to more than it. 12 is the smallest: 1 + 2 + 3 + 4 + 6 = 16. Some numbers can be written as the sum of two abundant numbers (the same one may be used twice, as in 24 = 12 + 12) and some cannot. Add up every positive integer from 1 to limit that cannot.

Implement non_abundant_sums(limit).

Find the divisor sums for every number at once with a sieve, list the abundant numbers, then mark every pair sum that stays within the limit.

Input

limit: The largest number to check.

Output

Return the sum of all n with 1 ≤ n ≤ limit that are not the sum of two abundant numbers.

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

No two abundant numbers add up to 23 or less, so every number counts: 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 and 30 = 12 + 18 are left out, so the answer is 465 − 24 − 30 = 411.

So gehst du vor

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

Hinweis 1

For each i, add i to the divisor sum of 2i, 3i, 4i, ...

Hinweis 2

Collect the abundant numbers in increasing order.

Hinweis 3

For each pair a ≤ b, stop the inner loop once a + b passes the limit.

Erwartete Komplexität

O(limit log limit + A²) time for A abundant numbers, O(limit) extra space

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.