Description：

一个合数的真因数是指这个数不包括其本身的所有因数，求区间真因数和。

$1\leqslant l\leqslant r\leqslant 5\times 10^9$

Solution：

真因数 $=$ 原数 $-$ 最小质因数，既然和最小质因数有关那么我们就可以考虑用 $\min\_25$ 筛求，在原 $\min\_25$ 筛中， $g(n,j)$ 表示 $1$ 到 $n$ 中最小质因子 $>j$ 的 $f$ 的个数以及质数，如果 $f(k)=k$ 的话，那么 $g(n,j)$ 就是 $1$ 到 $n$ 中最小质因子 $>j$ 的合数和所有质数的和，考虑在 $\min\_25$ 筛求区间素数之和的时候，转移为： $$ g(n,j)=g(n,j-1)-p_j\times \Bigl(g(\frac n{p_j},j-1)-g(p_j-1,j-1)\Bigr) $$ 在这个转移中，我们把所有的合数直接全部减掉了，后面那个括号里的表示的都是最小质因子为 $p_j$ 的数，这个时候我们可以发现 $g(\frac n{p_j},j-1)-g(p_j-1,j-1)$ 恰好就是他们这些数对答案的贡献，因此我们把这些数累加就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r;

ll n;

#define MAXN 1000010

int id1[MAXN],id2[MAXN];

ll w[MAXN];

int m = 0;

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int N;

int id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

ll s[MAXN];

void sieve(int n)

{

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		s[i] = s[i - 1];

		if(isprime[i])prime[++tot] = i,s[i] += i;

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

ll g[MAXN];

ll solve(ll nn)

{

	if(nn == 0)return 0;

	n = nn;

	N = sqrt(n);

	m = tot = 0;

	sieve(N);

	for(ll l = 1,r;l <= n;l = r + 1)

	{

		r = n / (n / l);

		w[++m] = n / l;

		if(w[m] <= N)id1[w[m]] = m;

		else id2[n / w[m]] = m;

		if(w[m] % 2 == 0)g[m] = w[m] / 2 * (w[m] + 1) - 1;

		else g[m] = (w[m] + 1) / 2 * w[m] - 1;

	}

	ll res = 0;

	for(int j = 1;j <= tot;++j)

	{

		res = res + g[id(n / prime[j])] - s[prime[j] - 1];

		for(int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

		{

			int k = id(w[i] / prime[j]);

			g[i] = g[i] - 1ll * prime[j] * (g[k] - s[prime[j] - 1]);

		}

	}

	return res;

}

int main()

{

	scanf("%lld%lld",&l,&r);

	cout << solve(r) - solve(l - 1) << endl;

	return 0;

}