UVa 160 - Factors and Factorials

// UVa 160 - Factors and Factorials

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int main() {
	bool prime[101];
	memset(prime, true, sizeof(prime));
	for (int i = 2; i <= 100; i++)
		if (prime[i]) {
			for (int j = i * i; j <= 100; j += i)
				prime[j] = false;
		}

	int f[101][101];
	memset(f, 0, sizeof(f));
	for (int i = 2; i <= 100; i++) {
		for (int j = 2; j <= 100; j++)
			f[i][j] = f[i - 1][j];
		int k = i;
		for (int j = 2; j <= i; j++)
			if (prime[j]) {
				while (k % j == 0) {
					k /= j;
					f[i][j]++;
				}
			}
	}

	int n;
	while ((cin >> n) && n) {
		printf("%3d! =", n);
		int k;
		for (k = 100; f[n][k] == 0; k--)
			;
		int c = 0;
		for (int j = 2; j <= k; j++)
			if (prime[j]) {
				printf("%3d", f[n][j]);
				c++;
				if (c % 15 == 0 && j < k)
					printf("\n      ");
			}
		printf("\n");
	}

	return 0;
}