Mittel 0 gelöst 0% Erfolgsquote

Euler's Totient

Count the integers from 1 to n that share no common factor with n.

Das lernst du

  • Find the distinct prime factors of n
  • Apply φ(n) = n × Π(1 − 1/p) with integers only
  • Handle n = 1 and prime n

Problem

Übersetzung anzeigen

Euler's totient function φ(n) counts the integers k with 1 ≤ k ≤ n and gcd(k, n) = 1. For example, φ(9) = 6, because 1, 2, 4, 5, 7 and 8 have no common factor with 9.

Implement eulers_totient(n).

Counting one k at a time is too slow for n up to 10^12. Use the product formula instead: φ(n) = n × (1 − 1/p) for every distinct prime p that divides n. Doing it in integers as n / p × (p − 1) avoids fractions.

Input

n: A positive integer.

Output

Return φ(n). By the definition φ(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², so φ(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 is prime, so every k from 1 to 12 is coprime to it and φ(13) = 12.

So gehst du vor

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

Hinweis 1

Factor n by trial division up to √n.

Hinweis 2

For each distinct prime p, replace the result by result / p × (p − 1); divide first so the value stays small.

Hinweis 3

A leftover factor above 1 after the loop is a prime too.

Erwartete Komplexität

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