GCD 2 - MarisaOJ: Marisa Online Judge

Count the number of integer pairs

$1 \le x, y \le n$ such that

$\text{gcd}(x, y)$ is a prime number. ### Input - A single line containing an integer

$n$ . ### Output - Print a single integer, which is the number of pairs that satisfy the condition. ### Constraints -

$1 \le n \le 2 \times 10^6$ . ### Example Input:

$4$

Output:

$4$

Topic

Math

Rating

1500

Solution (0)

Solution