Cod sursa(job #91702)
#include<stdio.h>
#define N 1000005
#define RAD 1100
int eu[N],prime[RAD],ciur[RAD],nr,n;
void eratostene(){
int i,j;
ciur[0]=ciur[1]=1;
for(i=2;i*i<RAD;++i)
if(!ciur[i])
for(j=i<<1;j<RAD;j+=i)
ciur[j]=1;
for(i=2;i<RAD;++i)
if(!ciur[i])
prime[nr++]=i;
/*
for(i=0;i<nr;++i)
printf("%d ",prime[i]);
*/
}
int caut(int x){//returneaza cel mai mic divizor prim al lui x
for(int i=0;prime[i]*prime[i]<=x;++i)
if(x%prime[i]==0)
return prime[i];
return x;
}
long long euler(int n){
int i,p;
long long s=1;
eu[1]=1;
for(i=2;i<=n;++i)
{
p=caut(i);
if(i%(p*p)==0)
eu[i]=eu[i/p]*p;
else
eu[i]=eu[i/p]*(p-1);
s+=eu[i]<<1;
}
return s;
}
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%d",&n);
eratostene();
printf("%lld\n",euler(n));
fclose(stdin);
fclose(stdout);
return 0;
}