#434. GCD

GCD

题目描述

给定正整数 nn,求 1x,yn1\le x,y\le ngcd(x,y)\gcd(x,y) 为素数的数对 (x,y)(x,y) 有多少对。

输入格式

只有一行一个整数,代表nn

输出格式

一行一个整数表示答案。

4
4

提示

样例输入输出 1 解释

对于样例,满足条件的 (x,y)(x,y)(2,2)(2,2)(2,4)(2,4)(3,3)(3,3)(4,2)(4,2)


数据规模与约定

  • 对于 100%100\% 的数据,保证 1n1071\le n\le10^7

来源:bzoj2818。

本题数据为洛谷自造数据,使用 CYaRon 耗时 55 分钟完成数据制作。