20111101

ACM 160 Factors and Factorials

質因數分解,階層版。
題目只要求到100!,
就偷懶一下。
先找出小於100的質數,
再做找質因數的動作。

/* ACM 160 Factors and Factorials
 * mythnc
 * 2011/11/01 20:15:27   
 * run time: 0.008
 */
#include <stdio.h>
 
#define MAXP 25
 
void init(int *);
void factor(int, int *, int *);
void printout(int, int *, int);
int size(int *);
 
int main(void)
{
    int n;
    int prime[] = { 2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
                   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                   73, 79, 83, 89, 97};
    int map[MAXP];
 
    while (scanf("%d", &n) && n != 0) {
        init(map);
        factor(n, prime, map);
        printout(n, map, size(map));
    }
    return 0;
}
 
/* init: initialize array m to zero */
void init(int *m)
{
    int i;
 
    for (i = 0; i < MAXP; i++)
        m[i] = 0;
}
 
/* factor: find prime factors */
void factor(int n, int *p, int *map)
{
    int i, j, tmp;
 
    for (i = 2; i < n + 1; i++) {
        tmp = i;
        for (j = 0; p[j] <= tmp; j++)
            while (tmp % p[j] == 0) {
                map[j]++;
                tmp /= p[j];
            }
    }
}
 
/* size: return the prime factors array m have */
int size(int *m)
{
    int i;
 
    for (i = MAXP - 1; m[i] == 0; i--)
        ;
 
    return i + 1;
}
 
/* printout: print out results */
void printout(int n, int *m, int count)
{
    int i;
 
    printf("%3d! =", n);
    for (i = 0; i < count; i++) {
        if (i == 15)
            printf("\n%6c", ' ');
        printf("%3d", m[i]);
    }
    printf("\n");
}

沒有留言: