21523_PrimeBases

Given any integer base b ≥ 2, it is well known that every positive integer n can be uniquely represented in base b. That is, we can write

n = a₀ + a₁*b + a₂*b*b + a₃*b*b*b + ...

where the coefficients a₀, a₁, a₂, a₃, ... are between 0 and b-1 (inclusive).

What is less well known is that if p₀, p₁, p₂, ... are the first primes (starting from 2, 3, 5, ...), every positive integer n can be represented uniquely in the "mixed" bases as:

n = a₀ + a₁*p₀ + a₂*p₀*p₁ + a₃*p₀*p₁*p₂ + ...

where each coefficient a_i is between 0 and p_i-1 (inclusive). Notice that, for example, a₃ is between 0 and p₃-1, even though p₃ may not be needed explicitly to represent the integer n.

Given a positive integer n, you are asked to write n in the representation above. Do not use more primes than it is needed to represent n, and omit all terms in which the coefficient is 0.

Each line of input consists of a single positive 32-bit signed integer. The end of input is indicated by a line containing the integer 0.

For each integer, print the integer, followed by a space, an equal sign, and a space, followed by the mixed base representation of the integer in the format shown below. The terms should be separated by a space, a plus sign, and a space. The output for each integer should appear on its own line.

123
456
123456
0

123 = 1 + 1*2 + 4*2*3*5
456 = 1*2*3 + 1*2*3*5 + 2*2*3*5*7
123456 = 1*2*3 + 6*2*3*5 + 4*2*3*5*7 + 1*2*3*5*7*11 + 4*2*3*5*7*11*13