Cod sursa(job #1113918)

Utilizator danny794Dan Danaila danny794 Data 21 februarie 2014 01:16:55
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>

using namespace std;

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

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 main() {
  freopen("fractii.in", "r", stdin);
  freopen("fractii.out", "w", stdout);
  get_sieve();
  int N;
  scanf("%d", &N);
  long long rez = 1;
  primes[1] = 1;
  for(int i = 2; i <= N; i++) {
    int k = i;
    for(int j = 1; j <= count; j++)
      if (k % sieve[j] == 0) {
        k /= sieve[j];
        if (k % sieve[j] == 0)
          primes[i] = primes[k] * sieve[j];
        else
          primes[i] = primes[k] * (sieve[j] - 1);
        break;
      }

    if (!primes[i])
      primes[i] = i - 1;
    rez += 2 * primes[i];
  }
  printf("%lld", rez);
  return 0;
}