Cod sursa(job #461898)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 8 iunie 2010 23:53:45
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<fstream.h>

short ciur[1000001];
long a[80000];
long n,i,j,m,aux;
long long sum,c,p;

int main()
{
	ifstream f("factii.in");
	ofstream g("fractii.out");
	f>>n;
	for (i=2;i<=n;i++)
	if (ciur[i]==0) 
		{
			for (j=i+i;j<=n;j+=i) ciur[j]=1;
			a[m++]=i;
		}
	sum=1;
	for (i=2;i<=n;++i)
	{
		if (ciur[i]==0) sum+=(i-1)*2;
		else 
		{
			aux=i;c=1;
			for (j=0;j<m,aux>1;j++)
			{
				p=1;
				while(aux%a[j]==0)
				{
					aux=aux/a[j];
					p*=a[j];
				}
				if (p*(a[j]-1)/a[j]>0) c*=p*(a[j]-1)/a[j];
			}
			sum+=c*2;
		}
	}
	g<<sum<<"\n";
	f.close();
	g.close();
}