学步园

//每一行增加的个数是欧拉函数的2倍
#include<stdio.h>
#define N 1000001
int a[N],b[N];
int main()
{
	int i,j,n;
	__int64 sum;
	 for(i=2;i<N;i++)
		 a[i]=i;
	 for(i=2;i<N;i++)
	 {
		 if(b[i]==1)continue;
		 a[i]=i-1;
		 for(j=i+i;j<N;j+=i)
		 {
			 b[j]=1;
			 a[j]=a[j]/i*(i-1);
		 }
	 }
	 while(scanf("%d",&n)!=-1)
	 {
	    sum=3;
		for(i=1;i<=n;i++)
			sum+=2*a[i];
		 printf("%I64d\n",sum);
	 }
	 return 0;
}