/*
Subject: #160 - Factors and Factorials
e-mail: morcavon@gmail.com
Homepage: http://www.morcavon.com
Building: 27/06/2005 ~ 28/06/2005
Last Update: 28/06/2005
*/
/*
<PURPOSE>
This program rad in a number N and
write out its factorial in terms of the numbers of the primes it contains.
Each line of output should contain fifteen numbers.
Any lines after first should be indented.
-
<PREDICATE>
2 <= N <= 100
-
<INPUT>
N
0
-
<OUTPUT>
N! = (list of the number of times each prime number occurs in N!)
*/
#include <iostream>
using namespace std;
#include <cstring>
#define ONLINE_JUDGE
#define PRIMECOUNT 25
void set_prime_pos(void);
void add(short result[], short occurs[]);
void print(short array[]);
void print2(short array[]);
short prime[PRIMECOUNT] = {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};
short prime_pos[101] = {0};
int main()
{
#if 1
short occurs[101][PRIMECOUNT + 1]; // 각 [][0]은 플래그 비트(계산된 N은 1로 표시)
short result[PRIMECOUNT];
int n, i, j, t;
set_prime_pos();
memset(occurs, 0, sizeof(short) * 101 * (PRIMECOUNT + 1));
// occurs[1][0] = 1;
while (cin >> n) {
if (n == 0)
break;
memset(result, 0, sizeof(short) * PRIMECOUNT);
// N부터 2까지의 소수가 나타나는 횟수를 구함(이미 계산된 경우는 넘어감)
for (i = n; i >= 2; i--) {
if (occurs[i][PRIMECOUNT] == 0) { // 아직 계산하지 않았을 경우...
t = i;
for (j = PRIMECOUNT - 1; j >= 0 && t > 1; ) {
if (t % prime[j] == 0) {
t /= prime[j];
occurs[i][j]++; // 해당 소수 카운트를 하나 증가시킴
continue; // j변동 없음
}
j--;
}
occurs[i][PRIMECOUNT] = 1; // flag 설정
#ifndef ONLINE_JUDGE
cout.width(3);
cout << i << ":";
print2(occurs[i]);
#endif
}
}
// occurs[2][] ~ occurs[n][] 까지 다 더한다=_=
for (i = 2; i <= n; i++) {
add(result, occurs[i]);
}
cout.width(3);
cout << n << "! =";
print(result);
}
#endif
return 0;
}
void add(short result[], short occurs[])
{
// result[]에 occurs[]의 각 원소를 다 더한다...
for (int i = 0; i < PRIMECOUNT; i++) {
// if (occurs[i] > 0)
result[i] += occurs[i];
}
}
void set_prime_pos()
{
for (int i = 0; i < PRIMECOUNT; i++) {
prime_pos[prime[i]] = i;
}
}
void print(short array[])
{
for (int i = 0; array[i] && i < PRIMECOUNT; ) {
cout.width(3);
cout << array[i];
if (++i == 15 && array[i])
cout << "\n ";
}
cout << '\n';
}
void print2(short array[])
{
for (int i = 0; i < PRIMECOUNT; i++) {
cout.width(3);
cout << array[i];
}
cout << '\n';
}
