游客 Signup | Login
中文 | En

2677 - 约数研究

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 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。

Input

输入文件common.in只一行一个整数N（2<=N<=5000000）。

Output

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

Examples

Input Format

5

Output Format

12

Solution C++

#include<bits/stdc++.h>
using namespace std;
long long n,s,m,t,a[5000005];
int main()
{
    cin>>n;a[1]=1;
    for(int i=2;i*i<=n;i++)
        if(a[i]==0)
          for(int j=2*i;j<=n;j+=i)
              a[j]++;
    for(int i=1;i<=n;i++)
    { 
    	m=sqrt(i);
    	if(a[i]==0)t+=i;
    	else 
    	{
    	   for(int j=2;j<=m;j++)
    	   if(i%j==0)
		   {
			  t+=j;
			  break;
		   }
	    }
	}
	cout<<t;
    return 0;
}
请先登陆