Cod sursa(job #146315)

Utilizator timotei21Timotei Dolean timotei21 Data 1 martie 2008 15:43:17
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
  
int prime[1000005];   
long long tot[1000005]={0, 1};   
  
void er(long long n)   
  
{ int i, j;   
for (i=2; i*i<=n; i++)   
    if (!prime[i])   
        for (j=2; i*j<=n; j++) prime[i*j]=i;   
}   
  
  
  
int main()   
{   
    long long n, nr=1, i, ci, d, p;   
    freopen("fractii.in", "r", stdin),
    freopen("fractii.out", "w",stdout);   
    scanf ("%lld", &n);   
    er(n);
    for (i=2; i<=n; ++i)   
        {   
            if (!prime[i]) tot[i]=i-1;   
            else {   
            ci=i;   
            d=prime[i];   
            while (ci%d==0) ci/=d;   
            tot[i]=(d-1)*( (i/ci)/d )*tot[ci];}   
            nr+=2*tot[i];   
        }   
    printf ("%lld\n", nr);
    return 0;
}