294 - Divisors - UVA

#include<iostream>
#include<cstdio>
#define MAX 40000
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int n_primos;
void init_crivo() {
 n_primos = 0;
 crivo[0] = crivo[1] = 1;
 for (int i = 2; i <= MAX; i++) {
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (int j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
 }
}
int NOD (int n) {
 if(n == 1) return 1;
 int r = 1, j;
 if(n <= MAX && !crivo[n]) return 2;
 for (int i = 0; primos[i] * primos[i] <= n; i++) {
  j = 0;
  while(n % primos[i] == 0) {
   n /= primos[i];
   j++;
  }
  r *= (j + 1);
  if(n == 1) return r;
 }
 if(r == 1) return 2;
 return r * 2;
}
int main() {
 int t, L, H, P, D;
 init_crivo();
 cin >> t;
 while(t--) {
  cin >> L >> H;
  D = P = 0;
  for (int i = L; i <= H; i++) {
   int nod = NOD(i);
   if(nod > D) D = nod, P = i;
  }
  printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, H, P, D);
 }
 return 0;
}