Cod sursa(job #29555)

Utilizator dodgerblueBogdan P. dodgerblue Data 9 martie 2007 15:51:45
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream.h>
int e[1001000],n;
long long int pr[1001000],num[1001000];
long long int s=1;
long long int r;

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

}

void prelucrare()
{
int i,j;

  for(i=1;i<=n;i++)
  {
    e[i]=1;
    pr[i]=1;
    num[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]==1)
   {
    pr[i]=i-1;
    for(j=2;j*i<=n;j++)
      {
  pr[i*j]*=i-1;
  num[i*j]*=i;
      }
   r=pr[i];
   }
   else
     r=pr[i]*i/num[i];
   s+=2*r;
  }

}

void afisare()
{
  ofstream g("fractii.out");
  g<<s<<"\n";
  g.close();
}

int main()
{
  citire();
  prelucrare();
  afisare();

  return 0;
}