시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB2781119649.741%

문제

메르센 수는 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+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjc8XC90ZD5cclxuXHRcdFx0PHRkPjEyOC0xID0gMTI3IC0gcHJpbWU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBQXHVhYzAwIFx1Y2RhOVx1YmQ4NFx1ZDc4OCBcdWQwNzAgXHVjMThjXHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHViYTU0XHViOTc0XHVjMTNjIFx1YzIxOFx1YjI5NCBcdWMxOGNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmQwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJhNTRcdWI5NzRcdWMxM2MgXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjMjE4XHViOTdjICYjMzk7XHViYTU0XHViOTc0XHVjMTNjIFx1ZDU2OVx1YzEzMVx1YzIxOCYjMzk7IFx1Yjc3YyBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YywgSygmbHQ7IDYzKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFBcdWFjMDAgSyBcdWM3NzRcdWQ1NThcdWM3NzggXHViYWE4XHViNGUwIFx1YmE1NFx1Yjk3NFx1YzEzYyBcdWQ1NjlcdWMxMzFcdWMyMThcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YmQ4NFx1ZDU3NFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNWQwXHViMjk0IFx1YjJlOCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoSyAmbHQ7IDYzKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlAmbHQ7PUsgXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWJhNTRcdWI5NzRcdWMxM2MgXHVkNTY5XHVjMTMxXHVjMjE4IDIgPHN1cD5QPFwvc3VwPi0xXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzE4Y1x1Yzc3OFx1YzIxOFx1YmQ4NFx1ZDU3NFx1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhNTRcdWI5NzRcdWMxM2MgXHVkNTY5XHVjMTMxXHVjMjE4IFx1Yzc5MFx1Y2NiNFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVjMjE4XHViZDgwXHVkMTMwIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YWMwMSBcdWMxOGNcdWM3NzhcdWMyMThcdWI0ZTRcdWM3NDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTE3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1lcnNlbm5lIENvbXBvc2l0ZSBOdW1iZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5PbmUgb2YgdGhlIHdvcmxkLXdpZGUgY29vcGVyYXRpdmUgY29tcHV0aW5nIHRhc2tzIGlzIHRoZSAmbGRxdW87R3JhbmQgSW50ZXJuZXQgTWVyc2VubmUgUHJpbWUgU2VhcmNoJnJkcXVvOyAmbWRhc2g7IEdJTVBTICZtZGFzaDsgc3RyaXZpbmcgdG8gZmluZCBldmVyLWxhcmdlciBwcmltZSBudW1iZXJzIGJ5IGV4YW1pbmluZyBhIHBhcnRpY3VsYXIgY2F0ZWdvcnkgb2Ygc3VjaCBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5BIE1lcnNlbm5lIG51bWJlciBpcyBkZWZpbmVkIGFzIGEgbnVtYmVyIG9mIHRoZSBmb3JtICgyPHN1cD5wPFwvc3VwPiZuZGFzaDsxKSwgd2hlcmUgcCBpcyBhIHByaW1lIG51bWJlciAmbWRhc2g7IGEgbnVtYmVyIGRpdmlzaWJsZSBvbmx5IGJ5IG9uZSBhbmQgaXRzZWxmLiAoQSBudW1iZXIgdGhhdCBjYW4gYmUgZGl2aWRlZCBieSBudW1iZXJzIG90aGVyIHRoYW4gaXRzZWxmIGFuZCBvbmUgYXJlIGNhbGxlZCAmbGRxdW87Y29tcG9zaXRlJnJkcXVvOyBudW1iZXJzLCBhbmQgZWFjaCBvZiB0aGVzZSBjYW4gYmUgdW5pcXVlbHkgcmVwcmVzZW50ZWQgYnkgdGhlIHByaW1lIG51bWJlcnMgdGhhdCBjYW4gYmUgbXVsdGlwbGllZCB0b2dldGhlciB0byBnZW5lcmF0ZSB0aGUgY29tcG9zaXRlIG51bWJlciAmbWRhc2g7IHJlZmVycmVkIHRvIGFzIGl0cyBwcmltZSBmYWN0b3JzLik8XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5IGl0IGxvb2tzIGFzIHRob3VnaCB0aGUgTWVyc2VubmUgbnVtYmVycyBhcmUgYWxsIHByaW1lcy48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjQwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlByaW1lPFwvdGg+XHJcblx0XHRcdDx0aD5Db3JyZXNwb25kaW5nIE1lcnNlbm5lIE51bWJlcjxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+NC0xID0gMyAtIHByaW1lPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjgtMSA9IDcgLSBwcmltZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD4zMi0xID0gMzEgLSBwcmltZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD43PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMjgtMSA9IDEyNyAtIHByaW1lPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5JZiwgaG93ZXZlciwgd2UgYXJlIGhhdmluZyBhICZsZHF1bztHcmFuZCBJbnRlcm5ldCZyZHF1bzsgc2VhcmNoLCB0aGF0IG11c3Qgbm90IGJlIHRoZSBjYXNlLjxcL3A+XHJcblxyXG48cD5XaGVyZSBrIGlzIGFuIGlucHV0IHBhcmFtZXRlciwgY29tcHV0ZSBhbGwgdGhlIE1lcnNlbm5lIGNvbXBvc2l0ZSBudW1iZXJzIGxlc3MgdGhhbiAyPHN1cD5rPFwvc3VwPiAmbWRhc2g7IHdoZXJlIGsgJmx0OyA2MyAodGhhdCBpcywgaXQgd2lsbCBmaXQgaW4gYSA2NC1iaXQgc2lnbmVkIGludGVnZXIgb24gdGhlIGNvbXB1dGVyKS4gSW4gSmF2YSwgdGhlICZsZHF1bztsb25nJnJkcXVvOyBkYXRhIHR5cGUgaXMgYSBzaWduZWQgNjQtYml0IGludGVnZXIuIFVuZGVyIGdjYyBhbmQgZysrIChDIGFuZCBDKysgaW4gdGhlIHByb2dyYW1taW5nIGNvbnRlc3QgZW52aXJvbm1lbnQpLCB0aGUgJmxkcXVvO2xvbmcgbG9uZyZyZHF1bzsgZGF0YSB0eXBlIGlzIGEgc2lnbmVkIDY0LWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyLCB3aXRob3V0IGxlYWRpbmcgb3IgdHJhaWxpbmcgYmxhbmtzLCBnaXZpbmcgdGhlIHZhbHVlIG9mIGsuIEFzIHByb21pc2VkLCBrICZsdDsgNjMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T25lIGxpbmUgcGVyIE1lcnNlbm5lIGNvbXBvc2l0ZSBudW1iZXIgZ2l2aW5nIGZpcnN0IHRoZSBwcmltZSBmYWN0b3JzIChpbiBpbmNyZWFzaW5nIG9yZGVyKSBzZXBhcmF0ZSBieSBhc3Rlcmlza3MsIGFuIGVxdWFsIHNpZ24sIHRoZSBNZXJzZW5uZSBudW1iZXIgaXRzZWxmLCBhbiBlcXVhbCBzaWduLCBhbmQgdGhlbiB0aGUgZXhwbGljaXQgc3RhdGVtZW50IG9mIHRoZSBNZXJzZW5uZSBudW1iZXIsIGFzIHNob3duIGluIHRoZSBzYW1wbGUgb3V0cHV0LiBVc2UgZXhhY3RseSB0aGlzIGZvcm1hdC4gTm90ZSB0aGF0IGFsbCBzZXBhcmF0aW5nIHdoaXRlIHNwYWNlIGZpZWxkcyBjb25zaXN0IG9mIG9uZSBibGFuay48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d