Home => ProblemSet => [bzoj2818]GCD
Problem2254--[bzoj2818]GCD

2254: [bzoj2818]GCD

Time Limit: 1 Sec  Memory Limit: 256 MB  Submit: 0  Solved: 4
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

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

Input

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

Output

一行一个整数表示答案。

Sample Input Copy 

4

Sample Output Copy 

4

HINT

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


  • 对于 100% 的数据，保证 1≤n≤107。


Source/Category

质数 欧拉函数 
[ Submit ] [ Status ]