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
qlines: one integerneach
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).