number theory – The problem from Ukrainian Selection Camp to the European Girls’ Olympiad in Informatics

Here is the link for the problem: https://www.e-olymp.com/ru/contests/20732/problems/224876
(everything there is in Ukrainian but maybe it will help you somehow)

The problem statement:

Given integer n (1≤n≤10^6),
you need to count the number of proper fractions where the denominator is less or equal to n

Fraction a/b is proper if it satisfies these properties:

  1. a, b are integers bigger or equal to 1
  2. a ≤ b
  3. a and b are coprime, GCD(a, b) == 1

Test cases:

Input:
5
Output:
10

Input:
10
Output:
32

For the first test case the fractions are:
1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5