Cod sursa(job #52758)

Utilizator dfsdeckStefan Oprea dfsdeck Data 19 aprilie 2007 21:11:52
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <fstream.h>
#include <math.h>
int m[1000000], N;
int find(int i, int j)
{	int k=i/j;
	int p=1;
	while(k%j==0)
	{	k/=j;
		p++;
	}
	k=i/j;
	return m[k]*(p+1)/p;
}
	
int main()
{	int i, j, k, ok;
	ifstream fin("fractii.in");
	ofstream fout("fractii.out");
	fin>>N;
	m[1]=1;
	for(i=2; i<=N; i++)
	{	k=sqrt(N);
		ok=1;
		for(j=2; (j<=k)&&ok; j++)
		{	if(i%j==0)
			{	m[i]=find(i, j);
				ok=0;
			}
		}
		if(ok)
			m[i]=2;
	}
	int s;
	s=1;
	for(i=2; i<=N; i++)
		s+=2*(i+1-m[i]);
	fout<<s<<'\n';
	fin.close();
	fout.close();
	return 0;
}