Skills101
← All coding problems

Euler's Totient

mediumMath & Number Theory+20 XPTime limit 3s

Euler's totient φ(n) counts the numbers from 1 to n that share no common factor with n (their gcd with n is 1). For example φ(9) = 6 — the numbers 1, 2, 4, 5, 7, 8 — and φ(1) = 1.

Answer many queries quickly.

Input:

  • line 1: q
  • next q lines: one integer n each

Output: q lines — φ(n) for each query.

Constraints: 1 ≤ q ≤ 10⁵, 1 ≤ n ≤ 10⁶.

Think about it: φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … over the distinct primes p dividing n. Compute it for every number at once with a sieve: start with phi[i] = i, and for each prime p do phi[k] -= phi[k] / p for every multiple k of p.

Sample input 1

3
9
1
10

Sample output 1

6
1
4

Sample input 2

2
7
12

Sample output 2

6
4

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.