시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 2 66.667%

문제

2보다 크거나 같은 자연수 b가 주어졌을 때, 모든 양의 정수 n을 b진법으로 표현하는 방법은 유일하다.

n = a0 + a1*b + a2*b*b + a3*b*b*b + ...

여기서 a0, a1, a2, a3, ...은 0보다 크거나 같고, b-1보다 작거나 같은 값을 가진다.

p0=2, p1=3, p2=5, ... 과 같이 pi를 i번째 소수라고 했을 때, 모든 양의 정수 n도 소수를 이용한 진법으로 유일하게 표현할 수 있다. 이를 소진법이라고 한다.

n = a0 + a1*p0 + a2*p0*p1 + a3*p0*p1*p2 + ...

여기서 a0, a1, a2, a3, ...은 0보다 크거나 같고, pi-1보다 작거나 같은 값을 가진다. 예를 들면, a3은 0보다 크거나 같고, p3-1보다 작거나 같다.

양의 정수 n이 주어졌을 때, 이를 소진법으로 나타내는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n을 포함하고 있다. n은 양의 정수로 231-1보다 작거나 같다. 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 수, 공백, 등호, 공백을 출력하고 문제 설명에 나온 것 같이 소진법으로 나타내 출력한다.

예제 입력

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

힌트