Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Eulersche Phi-Funktion

Zähle die ganzen Zahlen von 1 bis n, die mit n keinen gemeinsamen Teiler haben.

Das lernst du

  • Die verschiedenen Primfaktoren von n bestimmen
  • φ(n) = n × Π(1 − 1/p) nur mit ganzen Zahlen anwenden
  • n = 1 und Primzahlen n behandeln

Problem

Die Eulersche Phi-Funktion φ(n) zählt die ganzen Zahlen k mit 1 ≤ k ≤ n und ggT(k, n) = 1. Zum Beispiel ist φ(9) = 6, denn 1, 2, 4, 5, 7 und 8 haben mit 9 keinen gemeinsamen Teiler.

Implementiere eulers_totient(n).

Jedes k einzeln zu prüfen ist für n bis 10^12 zu langsam. Verwende stattdessen die Produktformel: φ(n) = n × (1 − 1/p) für jede verschiedene Primzahl p, die n teilt. Rechnest du das ganzzahlig als n / p × (p − 1), vermeidest du Brüche.

Eingabe

n: Eine positive ganze Zahl.

Ausgabe

Gib φ(n) zurück. Nach der Definition gilt φ(1) = 1.

Einschränkungen

1 ≤ n ≤ 10^12

Beispiele

Beispiel 1
Eingabe:
n = 36

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

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

Erwartete Ausgabe:
long expected = 12;

Erläuterung

36 = 2² × 3², also ist φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.

Beispiel 2
Eingabe:
n = 13

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

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

Erwartete Ausgabe:
long expected = 12;

Erläuterung

13 ist prim, also ist jedes k von 1 bis 12 teilerfremd zu 13, und φ(13) = 12.

So gehst du vor

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

Hinweis 1

Zerlege n per Probedivision bis √n in Primfaktoren.

Hinweis 2

Ersetze das Ergebnis für jede verschiedene Primzahl p durch Ergebnis / p × (p − 1); teile zuerst, damit der Wert klein bleibt.

Hinweis 3

Ein Restfaktor größer als 1 nach der Schleife ist ebenfalls eine Primzahl.

Erwartete Komplexität

Zeit O(√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.