시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 10 9 69.231%

문제

메르센 수는 2P-1 (P는 소수) 인 수를 말한다.

메르센 수는 P가 작을 땐 모두 소수인 듯 보인다.

Prime Corresponding Mersenne Number
2 4-1 = 3 - prime
3 8-1 = 7 - prime
5 32-1 = 31 - prime
7 128-1 = 127 - prime

하지만 P가 충분히 큰 소수일 경우, 메르센 수는 소수가 아닐 수도 있다.

이렇게 메르센 수이면서 소수가 아닌 수를 '메르센 합성수' 라 하자.

이 때, K(< 63)가 주어지면, P가 K 이하인 모든 메르센 합성수를 찾아 소인수분해하는 프로그램을 작성하여라.

입력

입력에는 단 하나의 정수 K가 주어진다. (K < 63)

출력

P<=K 인 모든 메르센 합성수 2 P-1에 대해, 예제 출력과 같은 형식으로 소인수분해한 결과를 출력한다.

메르센 합성수 자체가 작은 수부터 출력해야 하며, 각 소인수들은 오름차순으로 출력되어야 한다.

예제 입력 1

31

예제 출력 1

23 * 89 = 2047 = ( 2 ^ 11 ) - 1
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1
W3sicHJvYmxlbV9pZCI6IjkxNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhNTRcdWI5NzRcdWMxM2MgXHVkNTY5XHVjMTMxXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhNTRcdWI5NzRcdWMxM2MgXHVjMjE4XHViMjk0IDI8c3VwPlA8XC9zdXA+LTEgKFBcdWIyOTQgXHVjMThjXHVjMjE4KSBcdWM3NzggXHVjMjE4XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTU0XHViOTc0XHVjMTNjIFx1YzIxOFx1YjI5NCBQXHVhYzAwIFx1Yzc5MVx1Yzc0NCBcdWI1NTAgXHViYWE4XHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc3OCBcdWI0ZWYgXHViY2Y0XHVjNzc4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NDAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+UHJpbWU8XC90aD5cclxuXHRcdFx0PHRoPkNvcnJlc3BvbmRpbmcgTWVyc2VubmUgTnVtYmVyPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD40LTEgPSAzIC0gcHJpbWU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+OC0xID0gNyAtIHByaW1lPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjMyLTEgPSAzMSAtIHByaW1lPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjEyOC0xID0gMTI3IC0gcHJpbWU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBQXHVhYzAwIFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWQwNzAgXHVjMThjXHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHViYTU0XHViOTc0XHVjMTNjIFx1YzIxOFx1YjI5NCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmQwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJhNTRcdWI5NzRcdWMxM2MgXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjMjE4XHViOTdjICYjMzk7XHViYTU0XHViOTc0XHVjMTNjIFx1ZDU2OVx1YzEzMVx1YzIxOCYjMzk7IFx1Yjc3YyBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMsIEsoJmx0OyA2MylcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0LCBQXHVhYzAwIEsgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YmFhOFx1YjRlMCBcdWJhNTRcdWI5NzRcdWMxM2MgXHVkNTY5XHVjMTMxXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzU0NCBcdWMxOGNcdWM3NzhcdWMyMThcdWJkODRcdWQ1NzRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzVkMFx1YjI5NCBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKEsgJmx0OyA2Myk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QJmx0Oz1LIFx1Yzc3OCBcdWJhYThcdWI0ZTAgXHViYTU0XHViOTc0XHVjMTNjIFx1ZDU2OVx1YzEzMVx1YzIxOCAyIDxzdXA+UDxcL3N1cD4tMVx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWMxOGNcdWM3NzhcdWMyMThcdWJkODRcdWQ1NzRcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTU0XHViOTc0XHVjMTNjIFx1ZDU2OVx1YzEzMVx1YzIxOCBcdWM3OTBcdWNjYjRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1YmQ4MFx1ZDEzMCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWFjMDEgXHVjMThjXHVjNzc4XHVjMjE4XHViNGU0XHVjNzQwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkxNzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNZXJzZW5uZSBDb21wb3NpdGUgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+T25lIG9mIHRoZSB3b3JsZC13aWRlIGNvb3BlcmF0aXZlIGNvbXB1dGluZyB0YXNrcyBpcyB0aGUgJmxkcXVvO0dyYW5kIEludGVybmV0IE1lcnNlbm5lIFByaW1lIFNlYXJjaCZyZHF1bzsgJm1kYXNoOyBHSU1QUyAmbWRhc2g7IHN0cml2aW5nIHRvIGZpbmQgZXZlci1sYXJnZXIgcHJpbWUgbnVtYmVycyBieSBleGFtaW5pbmcgYSBwYXJ0aWN1bGFyIGNhdGVnb3J5IG9mIHN1Y2ggbnVtYmVycy48XC9wPlxyXG5cclxuPHA+QSBNZXJzZW5uZSBudW1iZXIgaXMgZGVmaW5lZCBhcyBhIG51bWJlciBvZiB0aGUgZm9ybSAoMjxzdXA+cDxcL3N1cD4mbmRhc2g7MSksIHdoZXJlIHAgaXMgYSBwcmltZSBudW1iZXIgJm1kYXNoOyBhIG51bWJlciBkaXZpc2libGUgb25seSBieSBvbmUgYW5kIGl0c2VsZi4gKEEgbnVtYmVyIHRoYXQgY2FuIGJlIGRpdmlkZWQgYnkgbnVtYmVycyBvdGhlciB0aGFuIGl0c2VsZiBhbmQgb25lIGFyZSBjYWxsZWQgJmxkcXVvO2NvbXBvc2l0ZSZyZHF1bzsgbnVtYmVycywgYW5kIGVhY2ggb2YgdGhlc2UgY2FuIGJlIHVuaXF1ZWx5IHJlcHJlc2VudGVkIGJ5IHRoZSBwcmltZSBudW1iZXJzIHRoYXQgY2FuIGJlIG11bHRpcGxpZWQgdG9nZXRoZXIgdG8gZ2VuZXJhdGUgdGhlIGNvbXBvc2l0ZSBudW1iZXIgJm1kYXNoOyByZWZlcnJlZCB0byBhcyBpdHMgcHJpbWUgZmFjdG9ycy4pPFwvcD5cclxuXHJcbjxwPkluaXRpYWxseSBpdCBsb29rcyBhcyB0aG91Z2ggdGhlIE1lcnNlbm5lIG51bWJlcnMgYXJlIGFsbCBwcmltZXMuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo0MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5QcmltZTxcL3RoPlxyXG5cdFx0XHQ8dGg+Q29ycmVzcG9uZGluZyBNZXJzZW5uZSBOdW1iZXI8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjQtMSA9IDMgLSBwcmltZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD44LTEgPSA3IC0gcHJpbWU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzItMSA9IDMxIC0gcHJpbWU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTI4LTEgPSAxMjcgLSBwcmltZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+SWYsIGhvd2V2ZXIsIHdlIGFyZSBoYXZpbmcgYSAmbGRxdW87R3JhbmQgSW50ZXJuZXQmcmRxdW87IHNlYXJjaCwgdGhhdCBtdXN0IG5vdCBiZSB0aGUgY2FzZS48XC9wPlxyXG5cclxuPHA+V2hlcmUgayBpcyBhbiBpbnB1dCBwYXJhbWV0ZXIsIGNvbXB1dGUgYWxsIHRoZSBNZXJzZW5uZSBjb21wb3NpdGUgbnVtYmVycyBsZXNzIHRoYW4gMjxzdXA+azxcL3N1cD4gJm1kYXNoOyB3aGVyZSBrICZsdDsgNjMgKHRoYXQgaXMsIGl0IHdpbGwgZml0IGluIGEgNjQtYml0IHNpZ25lZCBpbnRlZ2VyIG9uIHRoZSBjb21wdXRlcikuIEluIEphdmEsIHRoZSAmbGRxdW87bG9uZyZyZHF1bzsgZGF0YSB0eXBlIGlzIGEgc2lnbmVkIDY0LWJpdCBpbnRlZ2VyLiBVbmRlciBnY2MgYW5kIGcrKyAoQyBhbmQgQysrIGluIHRoZSBwcm9ncmFtbWluZyBjb250ZXN0IGVudmlyb25tZW50KSwgdGhlICZsZHF1bztsb25nIGxvbmcmcmRxdW87IGRhdGEgdHlwZSBpcyBhIHNpZ25lZCA2NC1iaXQgaW50ZWdlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkl0IGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlciwgd2l0aG91dCBsZWFkaW5nIG9yIHRyYWlsaW5nIGJsYW5rcywgZ2l2aW5nIHRoZSB2YWx1ZSBvZiBrLiBBcyBwcm9taXNlZCwgayAmbHQ7IDYzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uZSBsaW5lIHBlciBNZXJzZW5uZSBjb21wb3NpdGUgbnVtYmVyIGdpdmluZyBmaXJzdCB0aGUgcHJpbWUgZmFjdG9ycyAoaW4gaW5jcmVhc2luZyBvcmRlcikgc2VwYXJhdGUgYnkgYXN0ZXJpc2tzLCBhbiBlcXVhbCBzaWduLCB0aGUgTWVyc2VubmUgbnVtYmVyIGl0c2VsZiwgYW4gZXF1YWwgc2lnbiwgYW5kIHRoZW4gdGhlIGV4cGxpY2l0IHN0YXRlbWVudCBvZiB0aGUgTWVyc2VubmUgbnVtYmVyLCBhcyBzaG93biBpbiB0aGUgc2FtcGxlIG91dHB1dC4gVXNlIGV4YWN0bHkgdGhpcyBmb3JtYXQuIE5vdGUgdGhhdCBhbGwgc2VwYXJhdGluZyB3aGl0ZSBzcGFjZSBmaWVsZHMgY29uc2lzdCBvZiBvbmUgYmxhbmsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d