Pagini recente » Cod sursa (job #2574877) | Cod sursa (job #2542924) | Cod sursa (job #1798112) | Cod sursa (job #2803787) | Cod sursa (job #84410)
Cod sursa(job #84410)
#include<stdio.h>
#include<math.h>
#define MAX 1000001
#define NMAX 1000000
int t[1000002];
int p[78500], num = 1;
long n, nr;
char a[125000];
long long fr = 1;
void ciur()
{
int i, j;
for ( i = 4; i <= NMAX; i = i+2)
a[i>>3] |= ( 1<<(i&7) );
for ( i = 3; i <= NMAX; i = i+2)
{
if ( !(a[i>>3] & ( 1<<(i&7) ) ) )
for ( j = 2; j*i <= NMAX; j++)
a[ ( i*j ) >> 3] |= ( 1<<( ( i*j ) & 7 ));
}
p[1] = 2;
for ( i = 3; i <= NMAX; i = i+2 )
if ( !( a[i>>3] & ( 1<< (i&7) )))
p[++num] = i;
}
int main()
{
long i, ci, j;
int ex;
long long nr;
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%ld", &n);
ciur();
for (i = 1; i <= num; i++)
{
nr = p[i];
for (j = 1; nr <= MAX; j++)
{
t[nr] = (p[i] - 1) * (nr / p[i]);
nr *= p[i];
}
}
for ( i = 2; i <= n; i++)
if ( t[i] ==0)
{
ex = 1;
ci = i;
nr = 1;
for ( j = 1; ex; j++)
if ( ci % p[j] == 0)
{
ex = 0;
while (ci % p[j] == 0)
nr *= p[j], ci /= p[j];
}
t[i] = t[nr] * t[i/nr];
}
for ( i = 2; i <= n; i++)
fr += 2 * t[i];
printf("%lld", fr);
return 0;
}