10426: 约数研究
Description
科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩,小联被允许用“Samuel II”进行数学研究。
小联最近在研究和约数有关的问题,每个正整数N(N>=2)至少有两个约数,最小的一个是1,但小联并不关心它,因为所有正整数最小约数都是1。小联关心是正整数的第二小约数,并f(N)来表示,下表给出了一些f(N)的取值:
N |
2 |
3 |
4 |
5 |
F(N) |
2 |
3 |
2 |
5 |
现在小联希望用“Samuel II”来统计f(2) 到f(N)的累加和M。
Input
输入文件common.in只一行一个整数N(2<=N<=5000000)。
Output
Sample Input Copy
5
Sample Output Copy
12
HINT
30%的数据,N<=50,000
50%的数据,N<=1,000,000
100%的数据,N<2,000,000
第三题:有一定难度,考察学生对题意的理解以及经典算法筛选法的灵活应用,在算法中如何降低时间复杂度,用空间换取时间,当然不会筛选法本题也不会得0分。分析如下:
观察结论:一个正整数N(N>1)的第二小约数必定是一个素数。
方法一:暴力枚举(2~N),可以过两个点。
方法二:枚举(2~),可以过4个点。
方法三:利用“观察结论”枚举(2~),可以过6个点。
方法四:利用“观察结论”枚举素数表,可以过8个点。
方法五:利用“观察结论”筛选法:即把2的倍数标记为2,3的倍数标记为3,5的倍数标记为5,…,累加求和,可以过10个点。