T1

对于x质因数分解，如果只有一种质因子a，那x对答案的贡献即为a，否则为1

于是仿O(n log n)筛质数的方法，稍作修改就A了？

code:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 10000010;
int prime[N] , idx;
int L , R;
int gcd[N];
int main()
{
    scanf("%d%d" , &L , &R);
    for(int i = 2 ; i <= R ; i++)
    {
        if(gcd[i]) continue;
        gcd[i] = i;
        int now = i ;
        for(int j = 2 ; i * j <= R ; j++) gcd[i * j] = 1;
        for(int j = 2 ; (ll)now * i <= R ; j++)
        {
            now *= i;
            gcd[now] = i;
        }
    }
    long long sum = 0;
    for(int i = L ; i <= R; i++) sum += gcd[i];
    printf("%lld" , sum);
    return 0;
}