友情提示:380元/半年,儿童学编程,就上码丁实验室。
【题目描述】
一个合数的真因数是指这个数不包括其本身的所有因数,例如 $6$ 的正因数有$1,2,3,6$,其中真因数有 $1,2,3$。一个合数的最大真因数则是这个数的所有真因数中最大的一个,例如 $6$ 的最大真因数为 $3$。
给定正整数 $l$ 和 $r$,请你求出 $l$ 和 $r$ 之间(包括 $l$ 和 $r$)所有合数的最大真因数之和。
【输入】
输入共一行,包含两个正整数 $l$ 和 $r$。保证$l≤r$。
【输出】
输出共一行,包含一个整数,表示 $[l, r]$ 内所有合数的最大真因数之和。
【输入样例】
1 10
【输出样例】
17
【提示】
【样例解释1】
在 $1$ 至 $10$ 之间的合数有 $4,6,8,9,10$,它们的最大真因数分别为 $2,3,4,3,5$,因此最大真因数之和为 $2 + 3 + 4 + 3 + 5 = 17$。
【样例输入2】
101 1000
【样例输出2】
163446
【样例输入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$ |