Cod sursa(job #28383)

Utilizator dodgerblueBogdan P. dodgerblue Data 7 martie 2007 19:32:29
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<fstream.h>
int e[1000000],n;
long long int s=1,p;


int main()
{
  int i,j;

  ifstream f("fractii.in");
  f>>n;
  f.close();

  for(i=1;i<=n;i++)
    e[i]=1;

  for(i=2;i<=n/2;i++)
   if(e[i]==1)
    for(j=2;j*i<=n;j++)
      e[i*j]=0;


  for(i=2;i<=n;i++)
  {
   if(e[i]==0)
   {
    p=i;
    for(j=2;j<i;j++)
      if(e[j]==1 && i%j==0)
      {
	p*=j-1;
	p/=j;
      }
   }
   else
    p=i-1;
   s+=p*2;
  }


  ofstream g("fractii.out");
  g<<s<<"\n";
  g.close();
  return 0;
}