Cod sursa(job #34450)

Utilizator cezar305Mr. Noname cezar305 Data 20 martie 2007 19:39:21
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream.h>
#include <iomanip.h>
#include <math.h>
long long p[1000000],f[1000000],i,j,n,max,aux;
fstream in("fractii.in",ios::in);
fstream out("fractii.out",ios::out);
int main(){
 in>>n; max=(long long)sqrt(n);
 for (i=2;i<=max;i++){
   if (!p[i]){
     p[i]=1;f[i]=i-1;
     for (j=2;j<=n/i;j++){
       aux=i*j; 
       while (aux%i==0) aux=aux/i;
       if (aux==1) f[i*j]=(i-1)*j;    
       p[i*j]=aux;
     }      
   }       
 }    
 aux=0;
 for (i=2;i<=n;i++) {
   if (!f[i])
    if (p[i]) f[i]=f[p[i]]*f[i/p[i]];
    else f[i]=i-1;
   aux+=f[i];
 }          
 out<<2*aux+1;     
 in.close(); out.close();
return 0;
}