tax_game_bruteforce

#include <stdio.h>
#include <limits.h>
#include <string.h>

#define MAX 100
#define MIN 1

int PRIME[MAX] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int NUM[MAX] = {};
int test_num;
int final_ans;
int final_order[MAX] = {};

int find_max_factor(int x) {
  int prime_idx = 0;
  while (PRIME[prime_idx] * PRIME[prime_idx] <= x) {
    if (x % PRIME[prime_idx]) {
      prime_idx++;
    } else {
      int max_fac = x / PRIME[prime_idx];
      if (NUM[max_fac]) {
        NUM[max_fac] = 0;
        return max_fac;
      } else {
        prime_idx++;
      }
    }
  }

  if (NUM[1]) {
    return 1;
  }

  return x;
}

int min(int a, int b) {
  return a < b ? a : b;
}

void recursive(int depth, int used, int ans, int order[]) {
  if (used == 0) {

    printf("ans: %d\norder:", ans);
    for(size_t idx = 0; order[idx] != 0; ++idx) {
      printf("%d ", order[idx]);
    }
    printf("\n");

    if (ans < final_ans) {
      memcpy(final_order, order, sizeof(int) * depth);
      final_ans = ans;
    }
    return;
  }
  //printf("depth: %d, used: %d\n", depth, used);

  for (int idx = test_num; idx > 0; --idx) {
    if (!NUM[idx]){
      continue;
    } else {
      order[depth] = idx;
      int factor = find_max_factor(idx);
      NUM[factor] = 0;
      NUM[idx] = 0;
      ans += factor;
      int new_used = used - 1 - (!(factor == idx));
      recursive(depth+1, new_used, ans, order);
      ans -= factor;
      NUM[idx] = 1;
      NUM[factor] = 1;
      order[depth] = 0;
    }
  }
  return;
}

int main() {
  fprintf(stdout, "What number do you want to test? (%d ~ %d) ", MIN, MAX);
  fscanf(stdin, "%d", &test_num);

  if (test_num > MAX || test_num < MIN) {
    fprintf(stdout, "Input(%d) number is out of range! (%d ~ %d)", test_num, MIN, MAX);
    return 0;
  }

  // Initialize (Set NUM to unused)
  for (int idx = 1; idx <= test_num; ++idx) {
    NUM[idx] = 1;
    final_order[idx] = 0;
  }
  final_ans = INT_MAX;

  int order[MAX] = {};
  recursive(0, test_num, 0, order);

  fprintf(stdout, "Ans: %d\norder: ", final_ans);
  for(size_t idx = 0; final_order[idx] != 0; ++idx) {
    fprintf(stdout, "%d ", final_order[idx]);
  }
  fprintf(stdout, "\n");
  return 0;
}