#include "stdio.h"
int main(void)
{
FILE *fin, *fout;
if((fin = fopen("fractii.in", "r"))==NULL)
return 0;
if((fout = fopen("fractii.out", "w"))==NULL)
return 0;
unsigned int N, i, j, r;
register int m;
bool Eratostene[1000001];
register unsigned long long n, fi, p;
register unsigned int divizor[10];
fscanf(fin, "%d", &N);
int t[1000001];
for(i=0; i<=N; i++)
{
Eratostene[i] = true;
t[i] = 0;
}
t[1] = 1;
for(i=2; i*i<=N; i++)
{
if(Eratostene[i])
{
for(j=2; i*j<=N; j++)
Eratostene[i*j] = false;
}
}
for(i=2; i<=N; i++)
{
if(Eratostene[i])
{
t[i] = i-1;
unsigned long long k = i;
while(k<=N)
{
t[k] = (i-1)*((int)k/i);
k *= i;
}
}
}
for(i=2; i<=N; i++)
{
if(t[i] == 0)
{
for(j=2; j<=i; j++)
{
if(Eratostene[j])
{
p = i;
r = 0;
while(p%j==0)
{
p = p/j;
r++;
}
if(r>0 && t[p] != 0 && p%j!=0)
{
t[i] = t[p]*(j-1);
for(unsigned k=1; k<=r-1; k++)
t[i] *= j;
break;
}
}
}
}
}
n=N;
for(i=2; i<=N; i++)
{
fi = t[i];
m = N%i;
if(m == 0)
fi *= N/i;
else
{
fi *= N/i;
if(Eratostene[i])
fi += m;
else
{
if(m==1)
fi++;
else
{
r=0;
p=i;
for(j=2; j<=i; j++)
{
if(Eratostene[j] && p%j == 0)
{
while(p%j==0)
p = p/j;
divizor[r++] = j;
if(p==1)
break;
}
}
if((unsigned)m<divizor[0])
fi += m;
else
{
register long long k=0;
j=r-1;
while(divizor[j] >(unsigned) m)
j--;
r=j+1;
switch(r)
{
case 1:
{
k = m - m/divizor[0];
break;
}
case 2:
{
k = m - m/divizor[0] - m/divizor[1] + m / (divizor[0] * divizor[1]);
break;
}
case 3:
{
register int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2];
k = m - m/p1 - m/p2 - m/p3 + m/(p1*p2) + m/(p1*p3) + m/(p2*p3) - m/(p1*p2*p3);
break;
}
case 4:
{
register int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3];
k = m - m/p1 - m/p2 - m/p3 - m/p4 + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p2*p3) + m/(p2*p4) + m / (p3*p4) - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p3*p4) - m/(p2*p3*p4) + m/(p1*p2*p3*p4);
break;
}
case 5:
{
register int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3], p5 = divizor[4];
k = m - m/p1 - m/p2 - m/p3 - m/p4 -m/p5 + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p1*p5) + m/(p2*p3) + m/(p2*p4) + m/(p2*p5) + m / (p3*p4) + m/(p3*p5) + m/(p4*p5) - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p2*p5) - m/(p1*p3*p4) - m/(p1*p3*p5) - m/(p1*p4*p5) - m/(p2*p3*p4) - m/(p2*p3*p5) - m/(p2*p4*p5) - m/(p3*p4*p5);
k = k + m/(p1*p2*p3*p4) + m/(p1*p2*p3*p5) + m/(p1*p2*p4*p5) + m/(p1*p3*p4*p5) + m/(p2*p3*p4*p5) - m/(p1*p2*p3*p4*p5);
break;
}
case 6:
{
register int p1 = divizor[0], p2 = divizor[1], p3 = divizor[2], p4 = divizor[3], p5 = divizor[4], p6 = divizor[5];
k = m - m/p1 - m/p2 - m/p3 - m/p4 - m/p5 - m/p6;
k = k + m/(p1*p2) + m/(p1*p3) + m/(p1*p4) + m/(p1*p5) + m/(p1*p6) + m/(p2*p3) + m/(p2*p4) + m/(p2*p5) + m/(p2*p6) + m/(p3*p4) + m/(p3*p5) + m/(p3*p6) + m/(p4*p5) + m/(p4*p6) + m/(p5*p6);
k = k - m/(p1*p2*p3) - m/(p1*p2*p4) - m/(p1*p2*p5) - m/(p1*p2*p6) - m/(p1*p3*p4) - m/(p1*p3*p5) - m/(p1*p3*p6) - m/(p1*p4*p5) - m/(p1*p4*p6) - m/(p1*p5*p6) - m/(p2*p3*p4) - m/(p2*p3*p5) - m/(p2*p3*p6) - m/(p2*p4*p5) - m/(p2*p4*p6) - m/(p2*p5*p6) - m/(p3*p4*p5) - m/(p3*p4*p6) - m/(p3*p5*p6) - m/(p4*p5*p6);
k = k + m/(p1*p2*p3*p4) + m/(p1*p2*p3*p5) + m/(p1*p2*p3*p6) + m/(p1*p2*p4*p5) + m/(p1*p2*p4*p6) + m/(p1*p2*p5*p6) + m/(p1*p3*p4*p5) + m/(p1*p3*p4*p6) + m/(p1*p3*p5*p6) + m/(p1*p4*p5*p6) + m/(p2*p3*p4*p5) + m/(p2*p3*p4*p6) + m/(p2*p3*p5*p6) + m/(p2*p4*p5*p6) + m/(p3*p4*p5*p6);
k = k - m/(p1*p2*p3*p4*p5) - m/(p1*p2*p3*p4*p6) - m/(p6*p2*p3*p4*p5) - m/(p1*p6*p3*p4*p5) - m/(p1*p2*p6*p4*p5) - m/(p1*p2*p3*p6*p5) + m/(p1*p2*p3*p4*p5*p6);
break;
}
case 7:
{
register const int C71[7] = {0, 1, 2, 3, 4, 5, 6};
register const int C72[21][2] = {
{0, 1},
{0, 2},
{0, 3},
{0, 4},
{0, 5},
{0, 6},
{1, 2},
{1, 3},
{1, 4},
{1, 5},
{1, 6},
{2, 3},
{2, 4},
{2, 5},
{2, 6},
{3, 4},
{3, 5},
{3, 6},
{4, 5},
{4, 6},
{5, 6}
};
register const int C73[35][3] = {
{0, 1, 2},
{0, 1, 3},
{0, 1, 4},
{0, 1, 5},
{0, 1, 6},
{0, 2, 3},
{0, 2, 4},
{0, 2, 5},
{0, 2, 6},
{0, 3, 4},
{0, 3, 5},
{0, 3, 6},
{0, 4, 5},
{0, 4, 6},
{0, 5, 6},
{1, 2, 3},
{1, 2, 4},
{1, 2, 5},
{1, 2, 6},
{1, 3, 4},
{1, 3, 5},
{1, 3, 6},
{1, 4, 5},
{1, 4, 6},
{1, 5, 6},
{2, 3, 4},
{2, 3, 5},
{2, 3, 6},
{2, 4, 5},
{2, 4, 6},
{2, 5, 6},
{3, 4, 5},
{3, 4, 6},
{3, 5, 6},
{4, 5, 6}
};
register const int C74[35][4] = {
{0, 1, 2, 3},
{0, 1, 2, 4},
{0, 1, 2, 5},
{0, 1, 2, 6},
{0, 1, 3, 4},
{0, 1, 3, 5},
{0, 1, 3, 6},
{0, 1, 4, 5},
{0, 1, 4, 6},
{0, 1, 5, 6},
{0, 2, 3, 4},
{0, 2, 3, 5},
{0, 2, 3, 6},
{0, 2, 4, 5},
{0, 2, 4, 6},
{0, 2, 5, 6},
{0, 3, 4, 5},
{0, 3, 4, 6},
{0, 3, 5, 6},
{0, 4, 5, 6},
{1, 2, 3, 4},
{1, 2, 3, 5},
{1, 2, 3, 6},
{1, 2, 4, 5},
{1, 2, 4, 6},
{1, 2, 5, 6},
{1, 3, 4, 5},
{1, 3, 4, 6},
{1, 3, 5, 6},
{1, 4, 5, 6},
{2, 3, 4, 5},
{2, 3, 4, 6},
{2, 3, 5, 6},
{2, 4, 5, 6},
{3, 4, 5, 6}
};
register const int C75[21][5] = {
{0, 1, 2, 3, 4},
{0, 1, 2, 3, 5},
{0, 1, 2, 3, 6},
{0, 1, 2, 4, 5},
{0, 1, 2, 4, 6},
{0, 1, 2, 5, 6},
{0, 1, 3, 4, 5},
{0, 1, 3, 4, 6},
{0, 1, 3, 5, 6},
{0, 1, 4, 5, 6},
{0, 2, 3, 4, 5},
{0, 2, 3, 4, 6},
{0, 2, 3, 5, 6},
{0, 2, 4, 5, 6},
{0, 3, 4, 5, 6},
{1, 2, 3, 4, 5},
{1, 2, 3, 4, 6},
{1, 2, 3, 5, 6},
{1, 2, 4, 5, 6},
{1, 3, 4, 5, 6},
{2, 3, 4, 5, 6}
};
register const int C76[7][6] = {
{0, 1, 2, 3, 4, 5},
{0, 1, 2, 3, 4, 6},
{0, 1, 2, 3, 5, 6},
{0, 1, 2, 4, 5, 6},
{0, 1, 3, 4, 5, 6},
{0, 2, 3, 4, 5, 6},
{1, 2, 3, 4, 5, 6}
};
register int i, val = 0;
for(j=0; j<7; j++)
val += m/divizor[C71[j]];
k = m-val;
val = 0;
for(i=0; i<21; i++)
{
register int temp = 1;
for(j=0; j<2; j++)
temp *= divizor[C72[i][j]];
val += m/temp;
}
k += val;
val = 0;
for(i=0; i<35; i++)
{
register int temp = 1;
for(j=0; j<3; j++)
temp *= divizor[C73[i][j]];
val += m/temp;
}
k -= val;
val = 0;
for(i=0; i<35; i++)
{
register int temp = 1;
for(j=0; j<4; j++)
temp *= divizor[C74[i][j]];
val += m/temp;
}
k += val;
val = 0;
for(i=0; i<21; i++)
{
register int temp = 1;
for(j=0; j<5; j++)
temp *= divizor[C75[i][j]];
val += m/temp;
}
k -= val;
val = 0;
for(i=0; i<7; i++)
{
register int temp = 1;
for(j=0; j<6; j++)
temp *= divizor[C76[i][j]];
val += m/temp;
}
k += val;
k = k - m/(divizor[0]*divizor[1]*divizor[2]*divizor[3]*divizor[4]*divizor[5]*divizor[6]);
break;
}
default:
{
break;
}
}
fi += k;
}
}
}
}
n+=fi;
}
fprintf(fout, "%llu", n);
fclose(fin);
fclose(fout);
return 0;
}
Airinei Vasile airineiv