UVA 160 - Factors and Factorials

Factors and Factorials

The factorial of a number N (written N!) is defined as the product of all the integers from 1 to N. It is often defined recursively as follows:

Factorials grow very rapidly--5! = 120, 10! = 3,628,800. One way of specifying such large numbers is by specifying the number of times each prime number occurs in it, thus 825 could be specified as (0 1 2 0 1) meaning no twos, 1 three, 2 fives, no sevens and 1 eleven.

Write a program that will read in a number N ( ) and write out its factorial in terms of the numbers of the primes it contains.

Input

Input will consist of a series of lines, each line containing a single integer N. The file will be terminated by a line consisting of a single 0.

Output

Output will consist of a series of blocks of lines, one block for each line of the input. Each block will start with the number N, right justified in a field of width 3, and the characters `!', space, and `='. This will be followed by a list of the number of times each prime number occurs in N!.

These should be right justified in fields of width 3 and each line (except the last of a block, which may be shorter) should contain fifteen numbers. Any lines after the first should be indented. Follow the layout of the example shown below exactly.

Sample input

Sample output

  5! =  3  1  1

 53! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1

        1

#include <cstdio>

#include <cstring>

using namespace std;

bool isprime(int a)

{

	int i;

	for (i = 2; i*i <= a;i++)

	if (a%i == 0)

		return false;

	return true;

}

int prime[100], count[100];

int main()

{

	int n;

	int i,num;

	for (i = 2, num = 0; i <= 100;i++)

	if (isprime(i))

	{

		prime[num++] = i;

	}

	while (scanf("%d", &n) == 1 && n)

	{

		memset(count,0,sizeof(count));

		int maxn = 0;

		for (i = 2; i <= n; i++)

		{

			int m = i;

			int j;

			for (j = 0; j < num; j++)

			{

				while (m%prime[j] == 0)

				{

					m = m / prime[j];

					count[j]++;

					if (j>maxn)

						maxn = j;

				}

			}

		}

		printf("%3d! =", n);

		for (i = 0; i <= maxn; i++)

		{

			if (i == 15)

				printf("\n      ");

			printf("%3d", count[i]);

		}

		printf("\n");

	}

	return 0;

}

　　这道题应该特别注意输出格式。

巴特西

UVA 160 - Factors and Factorials

Input

Output

Sample input

Sample output

最新文章

热门文章