1. /* 
    2. phi(10)=5/5*(5-1)
    3. 数k被一个质数p整除：
    4. phi(k)=phi(k)/p*(p-1) 
    5. 这样子我们就把所有小于 sqrt(r) 的质数去掉了
    6. 但是还有一种情况：
    7. 比如 2*97 = 194,我们假设97>sqrt(r):phi(194)=194/2*1,此时还需要除去这个大质数的贡献。
    8. */
    9.     #include <cstdio>
    10.     #include <algorithm>
    11.     #include <cmath>
    12.     #include <cstring>
    13.     #include <cstdlib>
    14.     #include <iostream>
    15.     using namespace std;z
    16.     #define int long long 
    17.     inline int gi(){
    18.         char tmp=getchar();int ans=0;
    19.         while(!isdigit(tmp)) tmp=getchar();
    20.         while(isdigit(tmp)){
    21.             ans=ans*10+tmp-'0';
    22.             tmp=getchar();
    23.         }
    24.         return ans;
    25.     }
    26.     const int Mod = 666623333;
    27.     const int N = 4000200; 
    28.     int cnt,Prime[402000];bool Vis[8000202];
    29.     inline void Pre(){
    30.         for(int i=2;i<=5000000;++i){
    31.             if(!Vis[i])
    32.                 Prime[++cnt]=i;
    33.             for(int j=1;i*Prime[j]<=5000000 && j<=cnt ;++j){
    34.                 Vis[i*Prime[j]]=1;
    35.                 if(i%Prime[j]==0)
    36.                     break;    // 保证每一个数只会被最小的质因子筛去 
    37.             }
    38.         }
    39.     }
    40.     int Phi[N],Remain[N];
    41.     signed main()
    42.     {
    43.         int l,r;
    44.         l=gi(),r=gi();
    45.         Pre();
    46.         for(int i=l;i<=r;++i)
    47.             Phi[i-l]=i,Remain[i-l]=i;
    48.         for(int i=1;Prime[i]*Prime[i]<=r && i<=cnt;++i){ // 枚举素数
    49.             int p=Prime[i];
    50.             int st=l;
    51.             if(st%p!=0)
    52.                 st=(l/p)*p+p;
    53.             for(int j=st;j<=r;j+=p){
    54.     //            if(j==0) continue;    
    55.                 Phi[j-l]=(Phi[j-l]/p)*(p-1);
    56.                 while(Remain[j-l]%p==0)
    57.                     Remain[j-l]/=p;
    58.             }
    59.         }
    60.         int ans=0;
    61.         for(int i=l;i<=r;++i){
    62.             if(Remain[i-l]>1)
    63.                 Phi[i-l]=(Phi[i-l]/Remain[i-l])*(Remain[i-l]-1);
    64.             ans=(ans+(i-Phi[i-l])%Mod)%Mod;
    65.         }
    66.         printf("%lld",ans%Mod);
    67.         return 0;
    68.     }