最新消息:

信息学奥赛题库- 最大真因数

C++ 少儿编程 1254浏览 0评论

【题目描述】

一个合数的真因数是指这个数不包括其本身的所有因数,例如 $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$

您必须 登录 才能发表评论!