Problem E: 关于最大公约数的疑惑

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $127$ 正确数量 $17$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数论
小光是个十分喜欢素数的人,有一天他在学习最大公约数的时候突然想到了一个问题,他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y),即有多少(x,y),gcd(x,y)=素数,1<=x,y<=n。但是小光刚刚接触最大公约数,不能解决这个问题,于是他希望你能帮助他解决这个问题。
一个整数N  (1<=N<=10^5)
(x,y)的个数
5
5
(2,2) (2,4) (4,2) (3,3) (5,5)