2677 - 约数研究
时间限制 : 1 秒
内存限制 : 128 MB
科学家们在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。
题目输入
输入文件common.in只一行一个整数N（2<=N<=5000000）。
题目输出
输出文件common.out只一行一个整数M，即f(1)到f(N)的累加和
输入/输出样例
输入格式
5
输出格式
12
提示
【数据规模】
30%的数据，N<=50,000
50%的数据，N<=1,000,000
100%的数据，N<2,000,000
<p class="MsoNormal">
第三题：有一定难度，考察学生对题意的理解以及经典算法筛选法的灵活应用，在算法中如何降低时间复杂度，用空间换取时间，当然不会筛选法本题也不会得0分。分析如下：
</p>
<p class="MsoNormal">
观察结论：一个正整数N（N>1）的第二小约数必定是一个素数。
</p>
<p class="MsoNormal">
方法一：暴力枚举（2~N），可以过两个点。
</p>
<p class="MsoNormal">
方法二：枚举(2~<!--[if gte vml 1]><![endif]--><!--[if !vml]--><img width="47" height="24" src="http://tk.hustoj.com:80//../file://C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.gif" /><!--[endif]--><!--[if gte mso 9]><![endif]-->)，可以过4个点。
</p>
<p class="MsoNormal">
方法三：利用“观察结论”枚举(2~<!--[if gte vml 1]><![endif]--><!--[if !vml]--><img width="35" height="27" src="http://tk.hustoj.com:80//../file://C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image004.gif" /><!--[endif]--><!--[if gte mso 9]><![endif]-->)，可以过6个点。
</p>
<p class="MsoNormal">
方法四：利用“观察结论”枚举素数表，可以过8个点。
</p>
<p class="MsoNormal">
方法五：利用“观察结论”筛选法：即把2的倍数标记为2，3的倍数标记为3，5的倍数标记为5，…，累加求和，可以过10个点。
</p>