11960 - Divisor Game - UVA

#include<cstdio>
#define MAX 1009
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int maximos[1000001];
int numbers[1000001];
int n_primos = 0;
void init_crivo() {
 int i, j;
 for (i = 2; i <= MAX; i++) {
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
 }
}
int NOD(int n) {
 if(n == 1) return 1;
 if(n <= MAX && !crivo[n]) return 2;
 int j, r = 1;
 for (int i = 0; primos[i] * primos[i] <= n; i++) {
  j = 1;
  while(n % primos[i] == 0) {
   n /= primos[i];
   j++;
  }
  r *= j;
  if(n == 1) return r;
 }
 if(r == 1) return 2;
 return r * 2;
}
int main() {
 int k, t, n;
 init_crivo();
 for (int i = 1; i <= 1000000; i++) {
  maximos[i] = NOD(i);
  numbers[i] = maximos[i] >= maximos[numbers[i - 1]] ? i : numbers[i - 1];
 }
 scanf("%d", &t);
 for(k = 0; k < t; k++) {
  scanf("%d", &n);
  printf("%d\n", numbers[n]);
 }
 return 0;
}