最大真因数 - ROJ

【题目描述】

一个合数的真因数是指这个数不包括其本身的所有因数，例如 $6$ 的正因数有 $1,2,3,6$ ，其中真因数有 $1,2,3$ 。一个合数的最大真因数则是这个数的所有真因数中最大的一个，例如 $6$ 的最大真因数为 $3$ 。给定正整数 $l$ 和 $r$ ，请你求出 $l$ 和 $r$ 之间（包括 $l$ 和 $r$ ）所有合数的最大真因数之和。

【输入】

输入共一行，包含两个正整数 $l$ 和 $r$ 。保证 $l≤r$ 。

【输出】

输出共一行，包含一个整数，表示 $[l, r]$ 内所有合数的最大真因数之和。

【输入样例】

1 10

【输出样例】

【提示】

【样例解释1】在 $1$ 至 $10$ 之间的合数有 $4,6,8,9,10$ ，它们的最大真因数分别为 $2,3,4,3,5$ ，因此最大真因数之和为 $2 + 3 + 4 + 3 + 5 = 17$ 。【样例输入2】

101 1000

【样例输出2】

【样例输入3】

180208 975313

【样例输出3】

151642139152

【样例输入4】

339762200 340762189

【样例输出4】

112318862921546

【样例输入5】

2500000000 5000000000

【样例输出5】

3094668961678105770

【数据规模与约定】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。每个测试点的数据规模及特点如下表：

测试点编号	$l,r$	约定
$1$	$≤100$	无
$2$	$≤1000$
$3$	$≤10^4$
$4$	$≤10^5$
$5$	$≤5×10^6$
$6$	$≤10^7$
$7$	$≤10^9$	$r-l≤10^6$
$8$	$≤5×10^9$
$9$	$≤10^9$
$10$	$≤5×10^9$

101 1000

180208 975313

151642139152

339762200 340762189

112318862921546

2500000000 5000000000

3094668961678105770