Pagini recente » Cod sursa (job #385821) | Cod sursa (job #942877) | Cod sursa (job #1173292) | Cod sursa (job #412299) | Cod sursa (job #198132)
Cod sursa(job #198132)
#include <stdio.h>
int a[1000000];
long div (long a)
{
if (a%2==0) return 2;
int i;
for (i=3; i<=a/2; i+=2)
if (a%i==0) return i;
return 1;
}
int main()
{
long n, i, j ;
freopen ("fractii.in", "r", stdin);
scanf ("%ld", &n);
fclose(stdin);
a[0]=1;
long long s=1;
for (i=2; i<=n; ++i)
{
long d= div(i);
if (d!=1)
{
long x=1;
j=i;
while (j%d==0)
{
x*=d;
j/=d;
}
a[i-1]=(x-x/d)*a[j-1];
}
else a[i-1]=i-1;
s+=2*a[i-1];
}
freopen ("fractii.out", "w", stdout);
printf ("%lld", s);
fclose(stdout);
return 0;
}