令 \( s(n,j)=\sum\limits_{i=1}^{n}[min_i>=p_j]f(j) \) ，其中 \( min_i \) 表示 i 的最小质因子。
令 \( g(n,j)=\sum\limits_{i=1}^{n}[i \in P or min_i>p_j]1 \) ，其中 P 表示质数集合。
\( s(n,j)=s(n,j+1)+s(\frac{n}{p_j},j)+p_j(g(\frac{n}{p_j},cnt)-(j-1)) \) ，其中 cnt 表示 \( <=\sqrt n \) 的最大质数。
\( s(\frac{n}{p_j},j) \) 表示除掉 \( p_j \) 后是合数的数的贡献， \( g(\frac{n}{p_j},cnt)-(j-1) \) 表示除掉 \( p_j \) 后是一个 \( >=p_j \) 的质数的数的个数。
所以算 s 的时候要从小到大枚举 n 。如果每次从 m 开始枚举，在 n 较小的时候 continue 的话复杂度不对，但发现 j 是递减的，即 \( p_j \) 递减，所以每次最小的可行的 n 越来越小，用指针指一下就行了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N=;
ll n,p2[N],w[N],s[N],g[N];int m,cnt,base,p[N];bool vis[N];
void init()
{
m=cnt=;base=sqrt(n);
for(ll i=,j;i<=n;i=n/j+)w[++m]=j=n/i;
memset(vis,,sizeof vis);
for(int i=;i<=base;i++)
{
if(!vis[i])p[++cnt]=i,p2[cnt]=(ll)i*i;
for(int j=,d;j<=cnt&&(d=i*p[j])<=base;j++)
{vis[d]=;if(i%p[j]==)break;}
}
}
int Id(ll x){return x<=base?m-x+:n/x;}
void cz()
{
for(int i=;i<=m;i++)g[i]=w[i]-;
for(int j=,pl=;j<=cnt;j++,pl++)//pl=j-1
for(int i=;i<=m&&p2[j]<=w[i];i++)
g[i]-=g[Id(w[i]/p[j])]-pl;
}
ll solve()
{
init();cz();memset(s,,sizeof s);
int p0=;
for(int j=cnt;j;j--)
{
while(p0<=m&&p2[j]<=w[p0])p0++;
for(int i=p0-;i;i--)
{
int k=Id(w[i]/p[j]);
s[i]+=s[k]+(ll)p[j]*(g[k]-(j-));
}
}
return s[];
}
int main()
{
ll ans=;
scanf("%lld",&n);n--;if(n)ans=-solve();
scanf("%lld",&n);ans+=solve();
printf("%lld\n",ans);
return ;
}