1051.Easy Job

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <bitset>
using namespace std;

bitset<1000000> bs;
int p[78498];
int e[78498];
int m = 0;

void easy_job(int n) {
    int i, k = 0;
    int num;
    for (i = 0; i < 78498 && p[i] <= n; i++) {
        num = n;
        e[k] = 0;
        while (p[i] <= num) {
            e[k] += num / p[i];
            num /= p[i];
        }
        k++;
    }
    for (i = 0; i < k; i++) {
        printf("%d", p[i]);
        if (e[i] > 1)
            printf("^%d", e[i]);
        printf("%c", i != k - 1 ? '*' : '\n');
    }
}

int main(int argc, char** argv) {
    int n, i, j, cas = 1;

    bs.set();
    for (i = 2; i < 1000; i++) {
        if (bs.test(i)) {
            for (j = i * i; j < 1000000; j += i)
                bs.reset(j);
        }
    }
    for (i = 2; i < 1000000; i++)
        if (bs.test(i))
            p[m++] = i;

    scanf("%d", &n);
    while (n) {
        printf("Case %d:\n", cas++);
        easy_job(n);
        scanf("%d", &n);
    }

    return 0;
}