Cod sursa(job #28492)

Utilizator dodgerblueBogdan P. dodgerblue Data 7 martie 2007 21:34:26
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream.h>
int e[1001000],n;
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;
}