2012年8月24日

UVa 11466 - Largest Prime Divisor

Critical point : n should have more than one prime divisors.
For example : 16 : 2*2*2*2 , should print -1!

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

bool *prime = new bool[S];
int N = 0;
int *p = new int[664600];
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[N++] = i;
}

int main() {
  build();
  long long int n, max, tmp;
  while (scanf("%lld", &n) && n) {
    int i, times = 0;
    if (n < 0) n *= -1;
    tmp = n;
    max = -1;
    for (i = 0; i < N && n != 1; i++) {
      if (!(n % p[i]) && p[i] != tmp) {
        times++;
        while (!(n % p[i])) {
          n /= p[i];
          if (n == 1 && times > 1) {
            max = p[i];
            break;
          }
        }
      }
    }
    if (n != 1 && n != tmp) max = n;
    printf("%lld\n", max);
  }
  delete[] prime;
  delete[] p;
  return 0;
}

沒有留言:

張貼留言