gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <numeric>
#include <bitset>

using namespace std;

typedef unsigned long long ullong;
typedef long long llong;
typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

const int k_max = 12000;
const int sz = k_max;
bitset<sz/2> pbits;
vector<int> primes;

void setup();

int bests[k_max + 1];

void recurse(int prod, int sum, int n, int idx) {
  for (int i = idx; i <= k_max; ++i) {
    int prod2 = prod*i;
    if (prod2 >= 2*k_max) return;
    int sum2 = sum + i;
    int k = n + 1 + (prod2 - sum2);
    //if (k > k_max) return;
    if (k <= k_max) {
      bests[k] = min(bests[k], prod2);
    }
    recurse(prod2, sum2, n+1, i);
  }
}

int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);
  setup();

  // Note that worst case is for k=n is 2*n.
  for (int i = 2; i <= k_max; ++i) {
    bests[i] = 2*i;
  }

  for (int i = 2; i <= k_max; ++i) {
    recurse(i, i, 1, i);
  }
  int sum = 0;
  bool marked[2*k_max + 1];
  memset(marked, 0, sizeof(marked));
  for (int i = 2; i <= k_max; ++i) {
    if (!marked[bests[i]]) {
      sum += bests[i];
      marked[bests[i]] = true;
    }
  }
  putchar('\n');
  printf("%d\n", sum);

  return 0;
}

void setup () {
  pbits.set();
  const int cap = sqrt(sz) + 1;
  for (int i = 3; i < cap; i += 2) {
    if (pbits[i/2]) {
      for (int j = i*i/2; j < sz/2; j += i) {
        pbits.reset(j);
      }
    }
  }

  primes.push_back(2);
  for (int i = 1; i < sz/2; ++i) {
    if (pbits[i]) primes.push_back(2*i+1);
  }
}