Cod sursa(job #2779708)

Utilizator TghicaGhica Tudor Tghica Data 4 octombrie 2021 19:19:04
Problema Fractii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

int ciur[1000001];

int main() {
  ifstream cin("fractii.in");
  ofstream cout("fractii.out");
  int i, j;
  ciur[0] = 1;
  ciur[1] = 1;
  for( i = 2; i <= 1000000; i++ ) {
    if( ciur[i] == 0 ) {
      ciur[i] = 1;
      for( j = i + i; j <= 1000000; j += i ) {
        ciur[j] = i;
      }
    }
  }
  int n, k, p;
  long long prod, sum = 1;
  cin>>n;
  for( i = 2; i <= n; i++ ) {
    k = i;
    prod = 1;
    while( ciur[i] != 1 ) {
      p = ciur[i];
      i /= p;
      while( i % p == 0 ) {
        i /= p;
        prod *= p;
      }
      prod *= ( p - 1 );
    }
    if( i != 1 ) {
      prod *= ( i - 1 );
    }
    sum += prod * 2;
    i = k;
  }
  cout<<sum;
  return 0;
}