2012年8月20日

UVa 583 - Prime Factors

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

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 < 50000; i++)
    if (!prime[i])
      p[num++] = i;
}

int main() {
  build();
  int i, n;
  while (scanf("%d", &n) && n != 0) {
    printf("%d = ", n);
    if (n < 0) {
      printf("-1 x ");
      n *= -1;
    }
    if (n == 2147483647) {
      printf("%d\n", n);
      continue;
    }
    int first = 1, flag = 0;
    for (i = 0; n > 1 && i < num && p[i] <= n; i++) {
      while (n > 1 && n % p[i] == 0) {
        if (first == 1) printf("%d", p[i]);
        else printf(" x %d", p[i]);
        first = 0;
        n /= p[i];
        flag = 1;
      }
    }
    if (!flag)
      printf("%d", n);
    puts("");
  }
  delete[] p;
  delete[] prime;
  return 0;
}

沒有留言:

張貼留言