数论+埃氏筛+前缀和

题目分析：这道题目的难度只有一颗星，但是题目给的数据范围达到了1e7之多，暴力的时间复杂度达到了O（n^2），显然是不行的，所以这个题目需要优化+转化，我们不能被题目的表现所迷惑，题目里面有gcd，但是如果去求gcd的话时间复杂度肯定很高，所以这里用了十分巧妙地方法

1.首先我们用埃氏筛去筛选素数，这是一种十分强大的方法，每次都筛去素数的倍数
2.然后对其求前缀和，我们把素数的个数求出来，方法后面求素数对
3.接下来就是题目的核心思想，我们要求一共有所少个素数对，首先素数对中的素数是不能相同的，其次我们枚举每一个公约数，因为素数对的倍数也是符合题目要求，这样只需要求（2，n/g）范围就行，ans += sum[n / g] * (sum[n / g] - 1);减一的操作就是因为用了排列组合数学的思想
4.遍历每个g,找到两个不同的素数p1,p2,如果g * p1<=n 并且 g * p2<=n,那么（g * p1,g * p2）就是一个符合要求的素数对，那问题就转化成找 n/g 以内的素数的数量，可以通过线性筛出素数再处理前缀和得出。
5.对于每个含有公因子g的数，都去求一次素数对

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
int prime[maxn], sum[maxn];
void solve(int x)
{
    prime[0] = prime[1] = 1;
    for (int i = 2; i <= x; ++i)
    {
        if (!prime[i])
        {
            sum[i] = 1;
            for (int j = 2 * i; j <= x; j += i)
                prime[j] = 1;
        }
    }
}
int main()
{
    ll n, ans = 0;
    scanf("%lld", &n);
    solve(n);
    for (int i = 1; i <= n; ++i)
        sum[i] += sum[i - 1];
    for (int g = 1; g <= n; ++g)
        ans += sum[n / g] * (sum[n / g] - 1);
    printf("%lld\n", ans);
}