Cod sursa(job #279760)

Utilizator space.foldingAdrian Soucup space.folding Data 12 martie 2009 22:58:59
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.47 kb
#include <stdio.h>
int sir[1000], t[1000];

int main ()
{
  int nrfractii, nrfol, n, n_ant, i, j;

  freopen("fractii.in", "r", stdin);
  freopen("fractii.out", "w", stdout);
  scanf("%d", &n);
  nrfractii=1;
  t[1]=1;

  for(i=2;i<=n;i++)
  {
    if(sir[i]==0)
    {
      t[i]=i-1;
      for(j=i*i; j<=n; j*=i)
	t[j]=t[j/i]*t[i]*i;

      for(j=i*i; j<=n; j+=i)
	  sir[j]=1;
    }
    nrfractii+=2*t[i];
  }
  printf("%d", nrfractii);
  return 0;
}