//program fractii ireductibile

#include <iostream.h>
#include <conio.h>
#include <time.h>

int prim(long n){    
     int d=2; 
     if (!n) return 0;
     else
     while (d<=n/2) {
           if (n%d==0) return 0;
           else d++;}
     if (d==n/2+1) return 1;
}


int main(void){
    time_t start,finish;
    start=clock();
    float nr=0; 
    long n;
    float q=1;
    cout<<"n="; cin>>n;
    start=clock();
    for (int i=1 ; i<=n; i++){
                              q=1;
                              for (int j=1; j<=i; j++)
                              if (prim(j) && i%j==0 && j!=1) 
                                        q=q*(1-float(1)/float(j));
                              q=q*float(i);
                              nr=nr+2*q;
                              if (i==1) nr--;
                              }
     cout<<endl;                              
     cout<<"Numarul de fractii ireductibile este : "<<nr;
     finish=clock();
     cout<<endl;
     cout<<"Timpul de executie : "<<(double(finish-start))/(CLOCKS_PER_SEC);
     getch();
}