CodingGyan

Euler's Totient Function

medium Math and Number Theory

Problem

Print how many integers from 1 to n have gcd(i, n) = 1 (they share no factor with n except 1). For n = 1 the answer is 1.

Constraints

  • 1 <= n <= 10^12

Examples

Input

9

Output

6

Solutions

Best approachTime O(sqrt n)Space O(1)

Euler's formula is phi(n) = n * product of (1 - 1/p) over the different prime factors p. It needs only trial division up to sqrt(n). The values stay below 2^53, so JavaScript division stays exact here.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : The totient.
 * Approach: Factor n.
 * Time    : O(sqrt n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: Start with the result n and the number we will divide. We look for the prime factors of n.
        long result = n;
        long remaining = n;

        // Step 2: For every prime factor p, multiply the result by (1 - 1/p). In integers: result -= result / p.
        for (long p = 2; p * p <= remaining; p++) {
            if (remaining % p == 0) {
                while (remaining % p == 0) {
                    remaining /= p;
                }
                result -= result / p;
            }
        }

        // Step 3: What is left (if more than 1) is one last big prime factor.
        if (remaining > 1) {
            result -= result / remaining;
        }
        return result;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. Which numbers share a factor with n?

Try these next