Pagini recente » Cod sursa (job #2687037) | Cod sursa (job #790579) | Cod sursa (job #2464631) | Cod sursa (job #926044) | Cod sursa (job #82503)
Cod sursa(job #82503)
#include<stdio.h>
#include<math.h>
#define NMAX 1000
int p[170];
int num = 1;
long n, nr;
char a[1000];
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, r, ex;
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%ld", &n);
ciur();
for ( i = 2; i <= n; i++)
{
ci = i;
j = 1;
r = sqrt(ci);
nr = ci;
while ( ci != 1 && p[j] <= r)
{
ex = 1;
while ( ci > 1 && ci%p[j] == 0)
{
ci /= p[j];
ex = 0;
}
if ( ex == 0)
nr = ( nr / p[j] ) * ( p[j] - 1);
++j;
}
if ( ci > 1 )
nr = (nr / ci) * ( ci - 1 );
fr += 2 * nr;
}
printf("%lld", fr);
return 0;
}