2012年8月21日

UVa 160 - Factors and Factorials

A prime problem.

#include <stdio.h>

int p = 0, prime[110];

void build() {
  int i, j, tmp[110];
  for (i = 0; i < 110; i++)
    tmp[i] = 1;
  tmp[0] = 0;
  tmp[1] = 0;
  for (i = 2; i < 110; i++)
    if (tmp[i])
      for (j = i * i; j < 110; j += i)
        tmp[j] = 0;
  for (i = 0; i < 110; i++)
    if (tmp[i]) prime[p++] = i;
}

int main() {
  build();
  int i, j, n;
  while (scanf("%d", &n) && n) {
    int tmp, pNum[110] = {0};
    printf("%3d! =", n);
    for (i = n; i >= 2; i--) {
      tmp = i;
      for (j = 0; tmp > 1; j++)
        while (!(tmp % prime[j])) {
          pNum[j]++;
          tmp /= prime[j];
        }
    }
    for (i = 0; pNum[i]; i++) {
      if (i && !(i % 15)) printf("\n      ");
      printf("%3d", pNum[i]);
    }
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言