uva10699.c

#include <stdio.h>
#include <stdlib.h>

int primes[1000]; /*In fact, there's only 168 primes under 1000.*/
int p_idx = 0;

int is_prime(const int N) {
    int i;
    for (i=0; i<p_idx && primes[i]*primes[i] <= N; i++)
        if (N % primes[i] == 0)
            return 0;
    
    return 1;
}

void init_primes() {
    primes[0] = 2;
    primes[1] = 3;
    primes[2] = 5;
    
    p_idx = 3;
    
    int i;
    for (i=7; i*i < 1000000; i+=2)
        if (is_prime(i))
            primes[p_idx++] = i;
}

int main() {
    init_primes();
    
    int inp;
    while (scanf("%d", &inp)) {
        if (inp == 0) break;
        
        int query = inp;
        
        int cnt = 0;
        
        int i;
        for (i=0; i<p_idx && primes[i]*primes[i] <= query; i++) {
            if (query % primes[i] == 0) {
                cnt++;
                
                query = query / primes[i];
                while (query % primes[i] == 0)
                    query = query / primes[i];
            }
        }
        
        if (query != 1)
            cnt++;
            
        printf("%d : %d\n", inp, cnt);
    }
    
    return 0;
}