Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Sum of Proper Divisors

Add up every divisor of n that is smaller than n.

Das lernst du

  • Find divisors in pairs
  • Stop the loop at the square root
  • Avoid counting a square root divisor twice

Problem

Übersetzung anzeigen

The proper divisors of n are the positive divisors other than n itself. For 12 they are 1, 2, 3, 4 and 6. Their sum (sometimes called the aliquot sum) tells whether a number is perfect, abundant or deficient. Divisors come in pairs d and n / d, so you only need to try values of d up to the square root of n.

Implement sum_of_proper_divisors(n).

Input

n: A positive integer.

Output

Return the sum of all positive divisors of n that are less than n. For n = 1 there are none, so return 0.

Einschränkungen

1 ≤ n ≤ 10^12

Beispiele

Beispiel 1
Eingabe:
n = 12

Erwartete Ausgabe:
expected = 16
Eingabe:
long long n = 12;

Erwartete Ausgabe:
long long expected = 16;
Eingabe:
long n = 12;

Erwartete Ausgabe:
long expected = 16;

Erläuterung

1 + 2 + 3 + 4 + 6 = 16.

Beispiel 2
Eingabe:
n = 28

Erwartete Ausgabe:
expected = 28
Eingabe:
long long n = 28;

Erwartete Ausgabe:
long long expected = 28;
Eingabe:
long n = 28;

Erwartete Ausgabe:
long expected = 28;

Erläuterung

1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number.

So gehst du vor

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

Hinweis 1

If d divides n, then n / d divides n too.

Hinweis 2

Only try d up to the square root of n, adding both members of each pair.

Hinweis 3

Leave n itself out, and add the square root only once when n is a perfect square.

Erwartete Komplexität

O(sqrt n) time, O(1) 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.