ACM 10699 Count the factors

找質因數個數。

每次找到一個因數p後，就讓n = n / p，
再繼續對n做找因數的動作。
如此計算因數總數即為答案。

先建一個質數表再做會比較快。

/* ACM 10699 Count the factors
 * mythnc
 * 2011/12/29 09:41:28   
 * run time: 0.024
 */
#include <stdio.h>

int countp(int);

int main(void)
{
    int n;

    while (scanf("%d", &n) && n != 0)
        printf("%d : %d\n", n, countp(n));

    return 0;
}

/* countp: return the number of prime factor */
int countp(int n)
{
    int i, count;

    for (i = 2, count = 0; n != 1; i++) {
        if (n % i == 0) {
            count++;
            while (n % i == 0)
                n /= i;
        }
    }

    return count;
}