시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 119 50 39 50.649%

문제

홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다.

홍태석은 소수를 좋아하는 것으로 서강대에서 유명하기 때문에, 첫째 저금통에 들어있는 돈의 양과 둘째 저금통의 돈의 양을 이어붙였을 때, 그것이 소수가 되는 것을 너무나도 좋아한다.

예를 들어, 첫째 저금통에 12원이 있고, 둘째 저금통에 7원이 있다고 하자. 그럼 그 두 수를 이은 127은 소수가 된다.

이제, 최대한 소수가 많이 나오도록, 홍태석이 돈을 넣는 최적의 순서를 찾아내면 된다. 가장 처음에 두 저금통에는 1원씩 들어있다.

예를 들어,  N=4일 때를 보자.

1,1 → 2,1 → 2,2 → 3,2 → 3,3 → 4,3 → 4,4

위와같이 돈을 넣으면 소수는 오직 1번 등장한다. (43)

하지만, 다음과 같이 돈을 넣으면 소수는 3번 (31,41,43) 등장하게 된다.

1,1 → 2,1 → 3,1 → 4,1 → 4,2 → 4,3 → 4,4

위의 예가 N=4일 때 의 답이다. 가장 처음에 11은 세지 않는다.

입력

첫째 줄에 N이 주어진다. (1<=N<=999)

출력

첫째 줄에 소수가 가장 많이 나오는 저금 방법에서 소수가 나오는 횟수를 출력한다.

예제 입력 1

4

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI0MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDBcdWFlMDhcdWQxYjUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY0ZFx1ZDBkY1x1YzExZFx1Yzc0MCBcdWM4MDBcdWFlMDhcdWQxYjUgMlx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ2NGRcdWQwZGNcdWMxMWRcdWM3NDAgXHViOWU0XHVjNzdjXHViOWU0XHVjNzdjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MDBcdWFlMDhcdWQxYjVcdWM1ZDAgMVx1YzZkMFx1Yzc0NCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1YjQ1MCBcdWM4MDBcdWFlMDhcdWQxYjVcdWM1ZDAgXHViYWE4XHViNDUwIE5cdWM2ZDBcdWM3NzQgXHViYWE4XHVjNzc0XHViYTc0IFx1ZDBkY1x1YzExZFx1Yzc3NFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjN2E1XHViMDljXHVhYzEwXHVjNzQ0IFx1YzBiNCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjODAwXHVhZTA4XHVjNzQ0IFx1YmE0OFx1Y2Q5OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjRkXHVkMGRjXHVjMTFkXHVjNzQwIFx1YzE4Y1x1YzIxOFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzExY1x1YWMxNVx1YjMwMFx1YzVkMFx1YzExYyBcdWM3MjBcdWJhODVcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWNjYWJcdWM5ZjggXHVjODAwXHVhZTA4XHVkMWI1XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWIzYzhcdWM3NTggXHVjNTkxXHVhY2ZjIFx1YjQ1OFx1YzlmOCBcdWM4MDBcdWFlMDhcdWQxYjVcdWM3NTggXHViM2M4XHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWM3NzRcdWM1YjRcdWJkOTlcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWFkZjhcdWFjODNcdWM3NzQgXHVjMThjXHVjMjE4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NDQgXHViMTA4XHViYjM0XHViMDk4XHViM2M0IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjY2FiXHVjOWY4IFx1YzgwMFx1YWUwOFx1ZDFiNVx1YzVkMCAxMlx1YzZkMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM4MDBcdWFlMDhcdWQxYjVcdWM1ZDAgN1x1YzZkMFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZmMgXHVhZGY4IFx1YjQ1MCBcdWMyMThcdWI5N2MgXHVjNzc0XHVjNzQwIDEyN1x1Yzc0MCBcdWMxOGNcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWMxOGNcdWMyMThcdWFjMDAgXHViOWNlXHVjNzc0IFx1YjA5OFx1YzYyNFx1YjNjNFx1Yjg1ZCwgXHVkNjRkXHVkMGRjXHVjMTFkXHVjNzc0IFx1YjNjOFx1Yzc0NCBcdWIxMjNcdWIyOTQgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWIwYjRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YjQ1MCBcdWM4MDBcdWFlMDhcdWQxYjVcdWM1ZDBcdWIyOTQgMVx1YzZkMFx1YzUyOSBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZuYnNwO049NFx1Yzc3YyBcdWI1NGNcdWI5N2MgXHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD4xLDEgJnJhcnI7IDIsMSAmcmFycjsgMiwyICZyYXJyOyAzLDIgJnJhcnI7IDMsMyAmcmFycjsgNCwzICZyYXJyOyA0LDQ8XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNjQwXHVhYzE5XHVjNzc0IFx1YjNjOFx1Yzc0NCBcdWIxMjNcdWM3M2NcdWJhNzQgXHVjMThjXHVjMjE4XHViMjk0IFx1YzYyNFx1YzljMSAxXHViYzg4IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gKDQzKTxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViM2M4XHVjNzQ0IFx1YjEyM1x1YzczY1x1YmE3NCBcdWMxOGNcdWMyMThcdWIyOTQgM1x1YmM4OCAoMzEsNDEsNDMpIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEsMSAmcmFycjsgMiwxICZyYXJyOyAzLDEgJnJhcnI7IDQsMSAmcmFycjsgNCwyICZyYXJyOyA0LDMgJnJhcnI7IDQsNDxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjNjA4XHVhYzAwIE49NFx1Yzc3YyBcdWI1NGMgXHVjNzU4IFx1YjJmNVx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCAxMVx1Yzc0MCBcdWMxMzhcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbHQ7PU4mbHQ7PTk5OSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YjA5OFx1YzYyNFx1YjI5NCBcdWM4MDBcdWFlMDggXHViYzI5XHViYzk1XHVjNWQwXHVjMTFjIFx1YzE4Y1x1YzIxOFx1YWMwMCBcdWIwOThcdWM2MjRcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpZ2d5IEJhbmtzIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgT2xhZiBoYXMgdHdvIHBpZ2d5IGJhbmtzLiBFdmVyeSBkYXkgaGUgcHV0cyBvbmUgRXVybyBpbiBvbmUgb2YgdGhlIGJhbmtzIHVudGlsIGVhY2ggYmFuayBjb250YWlucyBOIEV1cm9zLiBUaGVuIGhlIGNhbiBidXkgYSBuZXcgdG95LjxcL3A+XHJcblxyXG48cD5MaXR0bGUgT2xhZiBhbHNvIGxpa2VzIHByaW1lIG51bWJlcnMuIFNvbWV0aW1lcywgdGhlIGFtb3VudCBvZiBFdXJvcyBpbiB0aGUgXHVmYjAxcnN0IGJhbmsgY29uY2F0ZW5hdGVkIHdpdGggdGhlIGFtb3VudCBvZiBFdXJvcyBpbiB0aGUgc2Vjb25kIGJhbmsgaXMgYSBwcmltZSBudW1iZXIuIEZvciBleGFtcGxlLCBpZiB0aGUgXHVmYjAxcnN0IGJhbmsgY29udGFpbnMgMTIgRXVyb3MgYW5kIHRoZSBzZWNvbmQgYmFuayBjb250YWlucyA3IEV1cm9zLCB0aGUgY29uY2F0ZW5hdGlvbiAxMjcgaXMgYSBwcmltZSBudW1iZXIuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBcdWZiMDFuZCBhbiBvcHRpbWFsIG9yZGVyIHRvIHB1dCB0aGUgRXVyb3MgaW4gdGhlIGJhbmtzIHNvIHRoYXQgYXMgbWFueSBwcmltZSBudW1iZXJzIGFzIHBvc3NpYmxlIGFwcGVhci4gSW5pdGlhbGx5LCBlYWNoIGJhbmsgY29udGFpbnMgMSBFdXJvLjxcL3A+XHJcblxyXG48cD5IZXJlIGlzIG9uZSBvcmRlciB0byBcdWZiMDFsbCB0aGUgYmFua3Mgd2hlbiBOID0gNDo8XC9wPlxyXG5cclxuPHA+MSwgMSAmcmFycjsgMiwgMSAmcmFycjsgMiwgMiAmcmFycjsgMywgMiAmcmFycjsgMywgMyAmcmFycjsgNCwgMyAmcmFycjsgNCwgNDxcL3A+XHJcblxyXG48cD5Pbmx5IG9uZSBwcmltZSBudW1iZXIgYXBwZWFyczogNDMuIFRoZSBmb2xsb3dpbmcgb3JkZXIgaXMgbXVjaCBiZXR0ZXI6PFwvcD5cclxuXHJcbjxwPjEsIDEgJnJhcnI7IDIsIDEgJnJhcnI7IDMsIDEgJnJhcnI7IDQsIDEgJnJhcnI7IDQsIDIgJnJhcnI7IDQsIDMgJnJhcnI7IDQsIDQ8XC9wPlxyXG5cclxuPHA+Tm93IHRocmVlIHByaW1lIG51bWJlcnMgYXBwZWFyOiAzMSwgNDEsIGFuZCA0My4gVGhpcyBpcyBhbiBvcHRpbWFsIFx1ZmIwMWxsaW5nIG9yZGVyIGZvciBOID0gNC4gTm90ZSB0aGF0IHRoZSBpbml0aWFsIDExIGlzIG5vdCBjb3VudGVkITxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBOOiB0aGUgbnVtYmVyIG9mIEV1cm9zIHRoYXQgZWFjaCBwaWdneSBiYW5rIHNob3VsZCBcdWZiMDFuYWxseSBjb250YWluLiZuYnNwOygxICZsZTsgTiAmbGU7IDk5OSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiBwcmltZSBudW1iZXJzIGluIGFuIG9wdGltYWwgXHVmYjAxbGxpbmcgb3JkZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 P2번