设 $a = gcd(a, b) \cdot x$ 、 $b = gcd(a, b) \cdot y$ 为某个 $x$ 和 $y$ 。

现在是 $F(a,b)=\frac{lcm(a, b)}{gcd(a, b)} = \frac{a \cdot b}{ gcd(a,b)^2} = x \cdot y$ .

由于 $F(a,b)$ - 是质数，那么 $x \cdot y$ - 也是质数。要使 $x \cdot y$ 是质数，那么其中一个数必须是质数，另一个数必须等于 $1$ 。我们的条件是 $a \lt b$ ，这意味着 $x = 1$ 和 $y$ 是质数。

我们得到 $a = gcd(a, b)$ , $b = gcd(a, b) \cdot y$ , 其中 $y$ - 是质数。

问题变为 --计算 $1 \leq gcd(a,b) \lt gcd(a,b) \cdot y \leq n$ 的数对 $(a,b)$ 。我们把 $y$ 固定下来，那么 $gcd(a,b)$ 可以取 $1$ 到 $\lfloor \frac{n}{y} \rfloor$ 中的任意值。因此，对于每个素数 $y$ 来说， $(a, b)$ 的合适配对数为 $\lfloor \frac{n}{y} \rfloor$ 。剩下的工作就是列举直到 $n$ 的所有素数。

在 $n \leq 10^7$ 的限制下，可以使用埃氏筛来完成。

$O(n \ log \ log \ n)$ .

#include <iostream>

using namespace std;

const int MAXN = 10000001;
bool prime[MAXN];

void solve() {
    int n, ans = 0;
    cin >> n;
    
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            ans += n / i;
        }
    }
    
    cout << ans << endl;
}

int main() {
    for (int i = 0; i < MAXN; i++) prime[i] = 1;
    prime[0] = prime[1] = 0;
	for (int i = 2; i * i < MAXN; i++) {
	    if (!prime[i]) continue;
	    for (int j = i * i; j < MAXN; j += i) 
            prime[j] = 0;
	}
	
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}