Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Dreieckszahl mit vielen Teilern

Finde die erste Dreieckszahl mit mindestens d Teilern.

Das lernst du

  • Die Teileranzahl aus der Primfaktorzerlegung bestimmen
  • Die Formel für Dreieckszahlen verwenden
  • Ein Produkt teilerfremder Faktoren getrennt behandeln

Problem

Dreieckszahlen geben an, wie viele Punkte ein Dreieck mit den Zeilenlängen 1, 2, 3, ... hat: T(1) = 1, T(2) = 3, T(3) = 6 und allgemein T(k) = k(k + 1) / 2. Geh sie der Reihe nach durch und halte bei der ersten an, die mindestens d positive Teiler hat (1 und die Zahl selbst zählen mit).

Implementiere highly_divisible_triangular(d).

Die Teiler einzeln zu zählen ist für die größeren Fälle zu langsam. Nutze stattdessen die Primfaktorzerlegung: Ist n = p^a × q^b × ..., dann hat n genau (a + 1)(b + 1)... Teiler. Da k und k + 1 teilerfremd sind, kannst du sie getrennt zerlegen.

Eingabe

d: Die benötigte Anzahl an Teilern.

Ausgabe

Gib die erste Dreieckszahl mit mindestens d Teilern zurück.

Einschränkungen

1 ≤ d ≤ 300

Beispiele

Beispiel 1
Eingabe:
d = 4

Erwartete Ausgabe:
expected = 6
Eingabe:
long long d = 4;

Erwartete Ausgabe:
long long expected = 6;
Eingabe:
long d = 4;

Erwartete Ausgabe:
long expected = 6;

Erläuterung

1 hat einen Teiler und 3 hat zwei, aber 6 hat vier (1, 2, 3, 6), also lautet die Antwort 6.

Beispiel 2
Eingabe:
d = 9

Erwartete Ausgabe:
expected = 36
Eingabe:
long long d = 9;

Erwartete Ausgabe:
long long expected = 36;
Eingabe:
long d = 9;

Erwartete Ausgabe:
long expected = 36;

Erläuterung

28 hat sechs Teiler, 36 = 2² × 3² hat dagegen 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), also lautet die Antwort 36.

So gehst du vor

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

Hinweis 1

T(k) = k(k + 1) / 2, und k und k + 1 haben keinen gemeinsamen Teiler.

Hinweis 2

Halbiere die gerade der beiden Zahlen k und k + 1 und zähle dann die Teiler jedes Teils.

Hinweis 3

Die Teileranzahl eines Produkts teilerfremder Zahlen ist das Produkt ihrer Teileranzahlen.

Erwartete Komplexität

Zeit O(K √K) bei K geprüften Dreieckszahlen, 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.