Cod sursa(job #64418)

Utilizator c_sebiSebastian Crisan c_sebi Data 3 iunie 2007 09:39:21
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>

int prime[1000005];
long long tot[1000005]={0, 1};

void er(long long n)

{ int i, j;
for (i=2; i*i<=n; i++)
	if (!prime[i])
		for (j=2; i*j<=n; j++) prime[i*j]=i;
}



int main()
{
	long long n, nr=1, i, ci, d, p;
	FILE *f=fopen("fractii.in", "r"), *g=fopen("fractii.out", "w");
	fscanf (f, "%lld", &n);
	fclose(f);
	er(n);
	for (i=2; i<=n; ++i)
		{
			if (!prime[i]) tot[i]=i-1;
			else {
			ci=i;
			d=prime[i];
			while (ci%d==0) ci/=d;
			tot[i]=(d-1)*( (i/ci)/d )*tot[ci];}
			nr+=2*tot[i];
		}
	fprintf (g, "%lld\n", nr);
	fclose(g);
	return 0;
}