Cod sursa(job #281468)

Utilizator zoltrixOLARU SABIN zoltrix Data 14 martie 2009 22:53:53
Problema Fractii Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
   #include <stdio.h>
   #include <fstream.h>

   char s[1000001];
   int t[1000001];

   int main ()
   {
     long double nrf;
     int i ,j, q, n;

     ifstream f("fractii.in");
     ofstream g ("fractii.out");
     f>>n;
     nrf=1;
     t[1]=1;

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

        for(j=i*2; j<=n; j+=i)
         {
	       s[j]=1;
               for(q=i; q<=n && j%q==0; q*=i)
                   if(!t[j] && (j/i)%q!=0)
                      t[j]=t[q]*t[j/q];
        }
       }
       nrf+=2*t[i];
     }
 g<<nrf;
 return 0;
 }