Cod sursa(job #82501)

Utilizator MarquiseMarquise Marquise Data 7 septembrie 2007 12:12:24
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#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("%ld", fr);
	return 0;
}