# UVa 516

## Summary

For this problem you have to know what the Prime Base Representation of a number is.

Use the Prime Sieve of Eratosthenes to create an array of all prime numbers less or equal than 32767, and then use the array to factor numbers.

## Explanation

For the Prime Base Representation of a number you have to print the prime factors of the number and the frequency they appear in it's factorization (in decreasing order of prime factors). Something like this:

${\displaystyle p_{n}e_{n}p_{n-1}e_{n-1}...p_{1}e_{1}}$

Where p is a decreasing sequence of primes and e is the corresponding sequence of powers of p. Each e must be greater than 0, so primes which are not factors are omitted from the prime base representation.

First you have to read a Prime Base Representation of a number ${\displaystyle x}$ and calculate ${\displaystyle x}$ just as you would expect by multiplying

${\displaystyle p_{n}^{e_{n}}\cdot p_{n-1}^{e_{n-1}}\cdot ...\cdot p_{1}^{e_{1}}}$

Then you have to output the Prime Base Representation of ${\displaystyle x-1}$.

For example, for the input

5 1 2 1

${\displaystyle x=5^{1}\cdot 2^{1}=10}$

Then ${\displaystyle x-1=9}$

and

${\displaystyle 9=3^{2}}$

Therefore, the output is

3 2

.

17 1
5 1 2 1
509 1 59 1
3 1
151 1 31 1 7 1
131 1 5 3 2 1
0

## Output

2 4
3 2
13 1 11 1 7 1 5 1 3 1 2 1
2 1
127 1 43 1 3 1 2 1
32749 1