1. #include <stdio.h>  
   2.   
   3. #include <vector>  
   4.   
   5. int n, i;  
   6. std::vector<int> primes, local_primes;  
   7. int prod, sign, sum;  
   8. long long total;  
   9. unsigned k;  
  10.   
  11. void back() {  
  12.   if (k == local_primes.size()) {  
  13.     if (!sign) sum += i / prod; else sum -= i / prod;  
  14.     return;  
  15.   }  
  16.   
  17.   k++; back(); k--;  
  18.     
  19.   prod *= local_primes[k];  
  20.   sign = sign ^ 1;  
  21.   k++; back(); k--;  
  22.   sign = sign ^ 1;  
  23.   prod /= local_primes[k];  
  24. }  
  25.   
  26. int main() {  
  27.   
  28.   FILE *f;  
  29.   f = fopen("fractii.in", "rt");  
  30.   fscanf(f, "%d", &n);  
  31.   fclose(f);  
  32.     
  33.   for (i = 2; i <= n; ++i) {  
  34.     int nr = i;  
  35.     local_primes.clear();  
  36.   
  37.     for (std::vector<int>::const_iterator it = primes.begin();  
  38.          it != primes.end() && (*it) * (*it) <= nr; ++it) {  
  39.       int j = *it;  
  40.       if (!(nr % j)) {  
  41.         local_primes.push_back(j);  
  42.         nr /= j;  
  43.         while (!(nr % j))  
  44.           nr /= j;  
  45.       }  
  46.     }  
  47.   
  48.     if (nr > 1)  
  49.       local_primes.push_back(nr);  
  50.   
  51.     if ((nr == i) && ((long long)nr * (long long)nr <= (long long)n)) {  
  52.       primes.push_back(nr);  
  53.     }  
  54.   
  55. #if 0  
  56.     // local primes should be sorted  
  57.     for (unsigned j = 1; j < local_primes.size(); ++j)  
  58.       if (local_primes[j - 1] >= local_primes[j])  
  59.         printf("bad1\n");  
  60. #endif  
  61.   
  62.     prod = 1; k = 0; sign = 0; sum = 0;  
  63.     back();  
  64.   
  65. #if 0  
  66.     // Sum should always be positive  
  67.     if (sum <= 0)  
  68.       printf("bad2\n");  
  69. #endif  
  70.   
  71. #if 0  
  72.     printf("%d : %d\n", i, sum);  
  73. #endif  
  74.   
  75.     total += 2 * sum;  
  76.   }  
  77.   
  78.   f = fopen("fractii.out", "wt");  
  79.   fprintf(f, "%lld\n", total + 1);  
  80.   fclose(f);  
  81.   
  82.   return 0;  
  83. }