10426: 约数研究

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩,小联被允许用“Samuel II”进行数学研究。

小联最近在研究和约数有关的问题,每个正整数NN>=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只一行一个整数N2<=N<=5000000)。

Output

输出文件common.out只一行一个整数M,即f(1)到f(N)的累加和

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个点。