Home => ProblemSet => 2.8-28:GCD
Problem2123--2.8-28:GCD

2123: 2.8-28:GCD

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ 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

样例解释：


对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=107


Source/Category

算法 质数 数论 
[ Submit ] [ Status ]