Cod sursa(job #696487)

Utilizator the_good90Patiu Dan the_good90 Data 28 februarie 2012 18:43:40
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include<math.h>
#include<fstream>
using namespace std;
int c[100000]={0},n,p=1;
void ciur()
{
	for(int i=2;i<=n;++i)
	   if(!c[i])
	       for(int j=i*i;j<=n;++j)
		       c[j]=1;
}	
int euler(int a)
{
	int s=sqrt(a),re=a;
	for(int i=2;i<=s;++i)
	    if(!c[i])
		    if(a%i==0)
			    re=re/i*(i-1);
 return re*2;
}

int main()
{
	ifstream in("fractii.in");
	ofstream out("fractii.out");
	in>>n;
	ciur();
	for(int i=2;i<=n;++i)
	    p+=euler(i);
	out<<p;
	return 0;
}