Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Summe der echten Teiler

Addiere alle Teiler von n, die kleiner als n sind.

Das lernst du

  • Teiler paarweise finden
  • Die Schleife bei der Quadratwurzel beenden
  • Einen Teiler, der genau die Quadratwurzel ist, nicht doppelt zählen

Problem

Die echten Teiler von n sind alle positiven Teiler außer n selbst. Für 12 sind das 1, 2, 3, 4 und 6. An ihrer Summe (auch Aliquotsumme genannt) erkennt man, ob eine Zahl vollkommen, abundant oder defizient ist. Teiler treten immer paarweise als d und n / d auf, deshalb musst du d nur bis zur Quadratwurzel von n durchprobieren.

Implementiere sum_of_proper_divisors(n).

Eingabe

n: Eine positive ganze Zahl.

Ausgabe

Gib die Summe aller positiven Teiler von n zurück, die kleiner als n sind. Für n = 1 gibt es keine, dann ist das Ergebnis 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, also ist 28 eine vollkommene Zahl.

So gehst du vor

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

Hinweis 1

Wenn d ein Teiler von n ist, dann ist auch n / d ein Teiler von n.

Hinweis 2

Probiere d nur bis zur Quadratwurzel von n und addiere jeweils beide Partner eines Paares.

Hinweis 3

Lass n selbst weg und addiere die Quadratwurzel nur einmal, wenn n eine Quadratzahl ist.

Erwartete Komplexität

Zeit O(sqrt n), zusätzlicher Speicher O(1)

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.