Cod sursa(job #149657)

Utilizator za_wolfpalianos cristian za_wolf Data 5 martie 2008 22:33:45
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.51 kb
#include<stdio.h>
#define NMAX 1001001
long s,x[NMAX],i,j,k,l,n,m;
int main()
{
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	scanf("%ld",&n);
	x[1]=1;
	for (i=2;i<=n;i++)
		if (x[i]==0)
			for (j=i+i;j<=n;j+=i)
				x[j]=1;
	x[0]=0;
	for (i=2;i<=n;i++)
		if (x[i]==0)
			x[++x[0]]=i;
	x[x[0]+1]=n+1;
	s=1;
	for (i=2;i<=n;i++)
	{
		k=i;
		for (j=1;x[j]<=i;j++)
			if (i%x[j]==0)
				k=k/x[j]*(x[j]-1);
		if (k==i) k--;
		s+=k+k;
	}
    printf("%ld\n",s);
	return 0;
}