A cryptographic key setup picks two distinct labels i and j from 1..n and only accepts the pair when they share no common factor greater than 1. Count how many unordered pairs (i, j) with 1 <= i < j <= n satisfy gcd(i, j) = 1.
A single line with one integer n.
A single integer: the number of coprime pairs (i, j) with 1 <= i < j <= n.
Example 1
Input
5
Expected
9
Explanation
Of the 10 pairs from 1..5, only (2,4) shares a common factor, so 9 pairs are coprime.
Example 2
Input
2
Expected
1
Explanation
The only pair is (1,2), and gcd(1,2)=1, 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 →