시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 21 21 75.000%

문제

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이 주어진다.

출력

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

예제 입력 1

123
456
123456
0

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjQ4MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWM5YzRcdWJjOTUiLCJkZXNjcmlwdGlvbiI6IjxwPjJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzQ0IGJcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm4gPSBhPHN1Yj4wPFwvc3ViPiArIGE8c3ViPjE8XC9zdWI+KmIgKyBhPHN1Yj4yPFwvc3ViPipiKmIgKyBhPHN1Yj4zPFwvc3ViPipiKmIqYiArIC4uLjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWMxMWMgYTxzdWI+MDxcL3N1Yj4sIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgYTxzdWI+MzxcL3N1Yj4sIC4uLlx1Yzc0MCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIGItMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPnA8c3ViPjA8XC9zdWI+PTIsIHA8c3ViPjE8XC9zdWI+PTMsIHA8c3ViPjI8XC9zdWI+PTUsIC4uLiBcdWFjZmMgXHVhYzE5XHVjNzc0IHA8c3ViPmk8XC9zdWI+XHViOTdjIGlcdWJjODhcdWM5ZjggXHVjMThjXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWIzYzQgXHVjMThjXHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1YyBcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjMThjXHVjOWM0XHViYzk1XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+biA9IGE8c3ViPjA8XC9zdWI+ICsgYTxzdWI+MTxcL3N1Yj4qcDxzdWI+MDxcL3N1Yj4gKyBhPHN1Yj4yPFwvc3ViPipwPHN1Yj4wKjxcL3N1Yj5wPHN1Yj4xPFwvc3ViPiArIGE8c3ViPjM8XC9zdWI+KnA8c3ViPjA8XC9zdWI+KnA8c3ViPjE8XC9zdWI+KnA8c3ViPjI8XC9zdWI+ICsgLi4uPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyZuYnNwO2E8c3ViPjA8XC9zdWI+LCBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIGE8c3ViPjM8XC9zdWI+LCAuLi5cdWM3NDAgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBwPHN1Yj5pPFwvc3ViPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljNFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgYTxzdWI+MzxcL3N1Yj5cdWM3NDAgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBwPHN1Yj4zPFwvc3ViPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHVjMThjXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIG5cdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gblx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIDI8c3VwPjMxPFwvc3VwPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOCwgXHVhY2Y1XHViYzMxLCBcdWI0ZjFcdWQ2MzgsIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2MjggXHVhYzgzIFx1YWMxOVx1Yzc3NCBcdWMxOGNcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4MzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltZSBCYXNlcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW55IGludGVnZXIgYmFzZSBiICZnZTsgMiwgaXQgaXMgd2VsbCBrbm93biB0aGF0IGV2ZXJ5IHBvc2l0aXZlIGludGVnZXIgbiBjYW4gYmUgdW5pcXVlbHkgcmVwcmVzZW50ZWQgaW4gYmFzZSBiLiBUaGF0IGlzLCB3ZSBjYW4gd3JpdGUmbmJzcDs8XC9wPlxyXG5cclxuPHA+biA9IGE8c3ViPjA8XC9zdWI+Jm5ic3A7KyBhPHN1Yj4xPFwvc3ViPipiICsgYTxzdWI+MjxcL3N1Yj4qYipiICsgYTxzdWI+MzxcL3N1Yj4qYipiKmIgKyAuLi48XC9wPlxyXG5cclxuPHA+d2hlcmUgdGhlIGNvZWZmaWNpZW50cyBhPHN1Yj4wPFwvc3ViPiwgYTxzdWI+MTxcL3N1Yj4sIGEyLCBhPHN1Yj4zPFwvc3ViPiwgLi4uIGFyZSBiZXR3ZWVuIDAgYW5kIGItMSAoaW5jbHVzaXZlKS48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyBsZXNzIHdlbGwga25vd24gaXMgdGhhdCBpZiBwPHN1Yj4wPFwvc3ViPiwgcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4gYXJlIHRoZSBmaXJzdCBwcmltZXMgKHN0YXJ0aW5nIGZyb20gMiwgMywgNSwgLi4uKSwgZXZlcnkgcG9zaXRpdmUgaW50ZWdlciBuIGNhbiBiZSByZXByZXNlbnRlZCB1bmlxdWVseSBpbiB0aGUgJnF1b3Q7bWl4ZWQmcXVvdDsgYmFzZXMgYXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPm4gPSBhPHN1Yj4wPFwvc3ViPiZuYnNwOysgYTxzdWI+MTxcL3N1Yj4qcDxzdWI+MDxcL3N1Yj4mbmJzcDsrIGE8c3ViPjI8XC9zdWI+KnA8c3ViPjAqPFwvc3ViPnA8c3ViPjE8XC9zdWI+Jm5ic3A7KyBhPHN1Yj4zPFwvc3ViPipwPHN1Yj4wPFwvc3ViPipwPHN1Yj4xPFwvc3ViPipwPHN1Yj4yPFwvc3ViPiZuYnNwOysgLi4uPFwvcD5cclxuXHJcbjxwPndoZXJlIGVhY2ggY29lZmZpY2llbnQgYWkgaXMgYmV0d2VlbiAwIGFuZCBwPHN1Yj5pPFwvc3ViPi0xIChpbmNsdXNpdmUpLiBOb3RpY2UgdGhhdCwgZm9yIGV4YW1wbGUsIGE8c3ViPjM8XC9zdWI+IGlzIGJldHdlZW4gMCBhbmQgcDxzdWI+MzxcL3N1Yj4tMSwgZXZlbiB0aG91Z2ggcDxzdWI+MzxcL3N1Yj4gbWF5IG5vdCBiZSBuZWVkZWQgZXhwbGljaXRseSB0byByZXByZXNlbnQgdGhlIGludGVnZXIgbi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHlvdSBhcmUgYXNrZWQgdG8gd3JpdGUgbiBpbiB0aGUgcmVwcmVzZW50YXRpb24gYWJvdmUuIERvIG5vdCB1c2UgbW9yZSBwcmltZXMgdGhhbiBpdCBpcyBuZWVkZWQgdG8gcmVwcmVzZW50IG4sIGFuZCBvbWl0IGFsbCB0ZXJtcyBpbiB3aGljaCB0aGUgY29lZmZpY2llbnQgaXMgMC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggbGluZSBvZiBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSBwb3NpdGl2ZSAzMi1iaXQgc2lnbmVkIGludGVnZXIuIFRoZSBlbmQgb2YgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHRoZSBpbnRlZ2VyIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW50ZWdlciwgcHJpbnQgdGhlIGludGVnZXIsIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGFuIGVxdWFsIHNpZ24sIGFuZCBhIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbWl4ZWQgYmFzZSByZXByZXNlbnRhdGlvbiBvZiB0aGUgaW50ZWdlciBpbiB0aGUgZm9ybWF0IHNob3duIGJlbG93LiBUaGUgdGVybXMgc2hvdWxkIGJlIHNlcGFyYXRlZCBieSBhIHNwYWNlLCBhIHBsdXMgc2lnbiwgYW5kIGEgc3BhY2UuIFRoZSBvdXRwdXQgZm9yIGVhY2ggaW50ZWdlciBzaG91bGQgYXBwZWFyIG9uIGl0cyBvd24gbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==