Problem 1147 --组合数学-莫比乌斯反演求GCD为质数

1147: 组合数学-莫比乌斯反演求GCD为质数

Time Limit: 3 Sec  Memory Limit: 256 MB
Submit: 11  Solved: 9
[Submit][Status][Web Board][Creator:]

Description

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

Input

一个整数N

Output

有多少对

Sample Input

4

Sample Output

4

HINT


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









上面的公式(4)(5)里面的后面两个n应该是N,公式(3)中的n也是N。



最后的公式解释:内层素数p求和。外层遍历所有的素数。对于公司(4),将n换成p。这样d是p的倍数,设d为k*p。则有 公式(5)的内层。




Source

[Submit][Status]