A scheduling system assigns time slots numbered 1 through n in a repeating cycle of length n. A slot k is considered 'independent' if gcd(k, n) == 1.
Given n, count how many integers k with 1 <= k <= n are independent (coprime to n). By convention, when n = 1, the only value k = 1 counts (its gcd with 1 is 1).
Line 1: a single integer n.
A single integer: the count of k in [1, n] with gcd(k, n) = 1.
Example 1
Input
9
Expected
6
Explanation
Numbers 1-9 coprime to 9 are 1,2,4,5,7,8 -> count 6.
Example 2
Input
1
Expected
1
Explanation
By convention, only k=1 is counted, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →