问题 D: 最大公约数

问题 D: 最大公约数

时间限制: 1 Sec  内存限制: 256 MB
提交: 32  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

给定整数 N，求 1≤x,y≤N 且 GCD(x,y) 为素数的数对 (x,y) 有多少对。

GCD(x,y)即求 x，y的最大公约数。

输入

输入一个整数 N。

输出

输出一个整数，表示满足条件的数对数量。

样例输入

4

样例输出

4

提示

1≤N≤10^7

[提交][状态]