Medium 0 solved 0% acceptance

Euler's Totient

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

What you'll learn

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

Problem

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.

Constraints

1 ≤ n ≤ 10^12

Examples

Example 1
Input:
n = 36

Expected output:
expected = 12
Input:
long long n = 36;

Expected output:
long long expected = 12;
Input:
long n = 36;

Expected output:
long expected = 12;

Explanation

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

Example 2
Input:
n = 13

Expected output:
expected = 12
Input:
long long n = 13;

Expected output:
long long expected = 12;
Input:
long n = 13;

Expected output:
long expected = 12;

Explanation

13 is prime, so every k from 1 to 12 is coprime to it and φ(13) = 12.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Factor n by trial division up to √n.

Hint 2

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

Hint 3

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

Expected complexity

O(√n) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.