Cod sursa(job #1113911)

Utilizator danny794Dan Danaila danny794 Data 21 februarie 2014 00:52:47
Problema Fractii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>

using namespace std;

bool test[1005];
int sieve[1005], count;

void get_sieve() {
  sieve[1] = 2;
  count = 1;
  test[2] = true;
  for(int i = 3; i <= 1000; i+=2)
    if( !test[i] ) {
      for(int j = i * i; j <= 1000; j+= i)
        test[j] = true;
      sieve[++count] = i;
    }
}

int get_primes(int N) {
  int i = 1, ret = N;
  while (sieve[i] * sieve[i] <= N && i <= count) {
    if (N % sieve[i] == 0) {
      while (N % sieve[i] == 0)
        N /= sieve[i];
      ret = ret  / sieve[i] * (sieve[i] - 1);
    }
    i++;
  }
  if (N > 1)
    ret = ret / N * (N - 1);
  return ret;
}

int main() {
  freopen("fractii.in", "r", stdin);
  freopen("fractii.out", "w", stdout);
  get_sieve();
  int N;
  scanf("%d", &N);
  long long rez = 1;
  for(int i = 2; i <= N; i++)
    rez += 2 * get_primes(i);
  printf("%lld", rez);
  return 0;
}