F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 2818. -- Gcd

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 7105  Solved: 3148
[Submit][Status][Discuss]

Description

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

hint

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


1<=N<=10^7

Source

湖北省队互测

[Submit][Status][Discuss]

HOME Back