Cod sursa(job #17960)

Utilizator cypryCiprian Oprisa cypry Data 17 februarie 2007 15:41:39
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>

long b[1000];

void descompune(long x)
{
 long d=2;;
 b[0]=0;
 while(x>1)
  {
   if(!(x%d))
    {
     b[0]++;
     b[b[0]]=d;
     while(!(x%d)) x/=d;
    }
   d++;
  }
}

long euler(long x)
{
 descompune(x);
 int i;
 long e=x;
 for(i=1;i<=b[0];i++)
  e=e*(b[i]-1)/b[i];
 return e;
}

long calculeaza(long n)
{
 long i,nr=1;
 for(i=2;i<=n;i++)
  nr+=2*euler(i);
 return nr;
}

int main(void)
{
 freopen("fractii.in","r",stdin);
 freopen("fractii.out","w",stdout);
 long n,nr;
 scanf("%ld",&n);
 nr=calculeaza(n);
 printf("%ld ",nr);
 fclose(stdin);
 fclose(stdout);
 return 0;
}