시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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이 주어진다.

출력

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

예제 입력 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOCwgXHVhY2Y1XHViYzMxLCBcdWI0ZjFcdWQ2MzgsIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2MjggXHVhYzgzIFx1YWMxOVx1Yzc3NCBcdWMxOGNcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODM5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJpbWUgQmFzZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFueSBpbnRlZ2VyIGJhc2UgYiAmZ2U7IDIsIGl0IGlzIHdlbGwga25vd24gdGhhdCBldmVyeSBwb3NpdGl2ZSBpbnRlZ2VyIG4gY2FuIGJlIHVuaXF1ZWx5IHJlcHJlc2VudGVkIGluIGJhc2UgYi4gVGhhdCBpcywgd2UgY2FuIHdyaXRlJm5ic3A7PFwvcD5cclxuXHJcbjxwPm4gPSBhPHN1Yj4wPFwvc3ViPiZuYnNwOysgYTxzdWI+MTxcL3N1Yj4qYiArIGE8c3ViPjI8XC9zdWI+KmIqYiArIGE8c3ViPjM8XC9zdWI+KmIqYipiICsgLi4uPFwvcD5cclxuXHJcbjxwPndoZXJlIHRoZSBjb2VmZmljaWVudHMgYTxzdWI+MDxcL3N1Yj4sIGE8c3ViPjE8XC9zdWI+LCBhMiwgYTxzdWI+MzxcL3N1Yj4sIC4uLiBhcmUgYmV0d2VlbiAwIGFuZCBiLTEgKGluY2x1c2l2ZSkuPFwvcD5cclxuXHJcbjxwPldoYXQgaXMgbGVzcyB3ZWxsIGtub3duIGlzIHRoYXQgaWYgcDxzdWI+MDxcL3N1Yj4sIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uIGFyZSB0aGUgZmlyc3QgcHJpbWVzIChzdGFydGluZyBmcm9tIDIsIDMsIDUsIC4uLiksIGV2ZXJ5IHBvc2l0aXZlIGludGVnZXIgbiBjYW4gYmUgcmVwcmVzZW50ZWQgdW5pcXVlbHkgaW4gdGhlICZxdW90O21peGVkJnF1b3Q7IGJhc2VzIGFzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5uID0gYTxzdWI+MDxcL3N1Yj4mbmJzcDsrIGE8c3ViPjE8XC9zdWI+KnA8c3ViPjA8XC9zdWI+Jm5ic3A7KyBhPHN1Yj4yPFwvc3ViPipwPHN1Yj4wKjxcL3N1Yj5wPHN1Yj4xPFwvc3ViPiZuYnNwOysgYTxzdWI+MzxcL3N1Yj4qcDxzdWI+MDxcL3N1Yj4qcDxzdWI+MTxcL3N1Yj4qcDxzdWI+MjxcL3N1Yj4mbmJzcDsrIC4uLjxcL3A+XHJcblxyXG48cD53aGVyZSBlYWNoIGNvZWZmaWNpZW50IGFpIGlzIGJldHdlZW4gMCBhbmQgcDxzdWI+aTxcL3N1Yj4tMSAoaW5jbHVzaXZlKS4gTm90aWNlIHRoYXQsIGZvciBleGFtcGxlLCBhPHN1Yj4zPFwvc3ViPiBpcyBiZXR3ZWVuIDAgYW5kIHA8c3ViPjM8XC9zdWI+LTEsIGV2ZW4gdGhvdWdoIHA8c3ViPjM8XC9zdWI+IG1heSBub3QgYmUgbmVlZGVkIGV4cGxpY2l0bHkgdG8gcmVwcmVzZW50IHRoZSBpbnRlZ2VyIG4uPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciBuLCB5b3UgYXJlIGFza2VkIHRvIHdyaXRlIG4gaW4gdGhlIHJlcHJlc2VudGF0aW9uIGFib3ZlLiBEbyBub3QgdXNlIG1vcmUgcHJpbWVzIHRoYW4gaXQgaXMgbmVlZGVkIHRvIHJlcHJlc2VudCBuLCBhbmQgb21pdCBhbGwgdGVybXMgaW4gd2hpY2ggdGhlIGNvZWZmaWNpZW50IGlzIDAuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgb2YgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgcG9zaXRpdmUgMzItYml0IHNpZ25lZCBpbnRlZ2VyLiBUaGUgZW5kIG9mIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyB0aGUgaW50ZWdlciAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGludGVnZXIsIHByaW50IHRoZSBpbnRlZ2VyLCBmb2xsb3dlZCBieSBhIHNwYWNlLCBhbiBlcXVhbCBzaWduLCBhbmQgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIG1peGVkIGJhc2UgcmVwcmVzZW50YXRpb24gb2YgdGhlIGludGVnZXIgaW4gdGhlIGZvcm1hdCBzaG93biBiZWxvdy4gVGhlIHRlcm1zIHNob3VsZCBiZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgYSBwbHVzIHNpZ24sIGFuZCBhIHNwYWNlLiBUaGUgb3V0cHV0IGZvciBlYWNoIGludGVnZXIgc2hvdWxkIGFwcGVhciBvbiBpdHMgb3duIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d