题解：CF2091E Interesting Ratio

求小于等于 $n$ 的所有自然数组成的数对 $(a,b)$ 中，$\mathrm{lcm}(a,b)\over\gcd(a,b)$ 是质数的无序对的个数。

注意到 $a=b$ 肯定不行，那么不妨令 $a<b$。

${\mathrm{lcm}(a,b)\over\gcd(a,b)} = {\mathrm{lcm}(a,b)\gcd(a,b)\over\gcd(a,b)\gcd(a,b)}={ab\over\gcd(a,b)\gcd(a,b)} = {a\over \gcd(a,b)}\times {b\over\gcd(a,b)}$。

两个整数的乘积是质数只有一种情况：小的那个是 $1$。因此 ${a\over\gcd(a,b)} = 1$，也就是说 $a = \gcd(a, b), b= \mathrm{lcm}(a, b)$。

换言之 $(a,b)$ 合法当且仅当 $b\over a$ 是个质数。那么对于每个 $b$，合法的 $a$ 的和 $b$ 的质因数一一对应。

枚举 $b$ 可以得到答案就是 $d(i)$ 的前缀和，其中 $d(i)$ 表示 $i$ 的不同质因数个数。

$d$ 能够有很多方法处理。一个比较简单的做法是做个线性筛。每次用质数 $p$ 筛合数的时候，若合数的另外一个乘数 $q$ 不是 $p$ 的倍数，则 $d(pq) = d(q)+1$。否则 $d(pq) = d(q)$。答案输出 $d$ 的前缀和即可。