#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a));

using namespace std;

const int maxn = 1e6 + 5, mod = 666623333;

int l, r;
long long res = 0;
bool is_prime[maxn + 5];
long long prime[maxn + 5], vis[maxn + 5], phi[maxn + 5], top = 0;

int main(){
    mem(is_prime, true);
    is_prime[1] = false;
    scanf("%d %d", &l, &r);
    for (int i = 2; i <= maxn; i++){
        if (is_prime[i]){
            prime[++top] = i;
        }
        for (int j = 1; j <= top && prime[j] * i <= maxn; j++){
            is_prime[prime[j] * i] = false;
            if (!(i % prime[j])){
                break;
            }
        }
    }
    for (int i = l; i <= r; i++){
        vis[i] = phi[i] = i;
    }
    for (int i = 1; i <= top && prime[i] * prime[i] <= r; i++){
        int temp = prime[i], b = l;
        if (l % temp){
            b = l / temp * temp + temp;
        }
        for (int j = b; j <= r; j += temp){
            phi[j] = phi[j] / temp * (temp - 1);
            while (!(vis[j] % temp)){
                vis[j] /= temp;
            }
        }
    }
    for (int i = l; i <= r; i++){
        if (vis[i] > 1){
            phi[i] = phi[i] / vis[i] * (vis[i] - 1);
        }
        res = (res + (i - phi[i]) % mod) % mod;
    }
    printf("%lld", res);

return 0;
}

其中的phi和vis数组会越界，但第二篇题解中这样写是可以过的。