P2568 GCD

Given a positive integer $n$, count the number of pairs $(x, y)$ such that $1\le x, y\le n$ and $\gcd(x,y)$ is a prime number.

A single line containing one integer representing $n$.

Output a single integer in one line, representing the answer.

#### Sample Input/Output 1 Explanation For the sample, the pairs $(x, y)$ that satisfy the condition are $(2, 2)$, $(2, 4)$, $(3, 3)$, $(4, 2)$. --- #### Constraints - For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^7$. --- Source: bzoj2818. The testdata for this problem are self-made by Luogu, generated using [CYaRon](https://github.com/luogu-dev/cyaron), taking 5 minutes. Translated by ChatGPT 5