Cod sursa(job #27864)

Utilizator MipiCornea Mihai Mipi Data 7 martie 2007 10:57:33
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream.h>
#define lun 10000004

ifstream f("fractii.in");
ofstream g("fractii.out");

long long n,sum;

int v[lun];
long long prim[lun],adr=1;

void filtrare(long n)
{
 prim[adr++]=2;
 int ok=1;
 long int pas=2,poz=2;
 v[1]=0;
 while(ok)
 {
  ok=0;
  for(long long i=poz*poz;i<=n;i+=pas)
   v[i]=0;
  for(long long j=poz+1;j<=n;j++)
   if(v[j])
   {
    poz=pas=j;
    prim[adr++]=j;
    ok=1;
    break;
   }
 }
}

long int tot(int nr)
{
 long int pr=nr;
 for(long int i=1;prim[i]<=nr;i++)
  if(nr%prim[i]==0)
   pr=pr-(pr/prim[i]);
 return pr;
}

int main()
{
 memset(v,1,sizeof(v));
 memset(prim,9999999,sizeof(prim));
 f>>n;
 filtrare(n);
 long long sum=1;
 for(long int i=2;i<=n;i++)
  sum+=tot(i)*2;
 g<<sum;
 g.close();
 return 0;
}