2012年8月20日

UVa 294 - Divisors


#include <stdio.h>
#include <math.h>
#define S 35000

bool *prime = new bool[S];
int *p = new int[S], num = 0;
void build() {
  long long int i, j, k, s = sqrt(S);
  prime[0] = true;
  prime[1] = true;
  for (i = 2; i <= s; i++)
    if (!prime[i])
      for (k = (S - 1) / i, j = i * k; k >= i; k--, j -= i)
        if (!prime[k])
          prime[j] = true;
  for (i = 0; i < S; i++)
    if (!prime[i])
      p[num++] = i;
}
int div(int n) {
  if (n == 1) return 1;
  int i, ans = 0, tmp;
  for (i = 0; i < num && p[i] <= n; i++) {
    tmp = 0;
    while (n % p[i] == 0) {
      tmp++;
      n /= p[i];
    }
    if (!ans && tmp)
      ans = 1;
    ans *= (tmp + 1);
  }
  return ans;
}
int main() {
  build();
  int i, a, b, n;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &a, &b);
    int tmp, max = 0, ans;
    for (i = a; i <= b; i++) {
      tmp = div(i);
      if (tmp > max) {
        max = tmp;
        ans = i;
      }
    }
    printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, ans, max);
  }
  return 0;
}

沒有留言:

張貼留言