题目描述

给定正整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

输入格式

只有一行一个整数，代表 $n$。

输出格式

一行一个整数表示答案。

4

4

提示

样例输入输出 1 解释

对于样例，满足条件的 $(x,y)$ 为 $(2,2)$，$(2,4)$，$(3,3)$，$(4,2)$。

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1\le n\le10^7$。

来源：bzoj2818。

本题数据为洛谷自造数据，使用 CYaRon 耗时 $5$ 分钟完成数据制作。