시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 31095 13227 10966 43.927%

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

제한

  • 1 ≤ n ≤ 123,456

예제 입력 1

1
10
13
100
1000
10000
100000
0

예제 출력 1

1
4
3
21
135
1033
8392
W3sicHJvYmxlbV9pZCI6IjQ5NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYTBcdWI5NzRcdWQyYjhcdWI3OTEgXHVhY2Y1XHVjOTAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjYTBcdWI5NzRcdWQyYjhcdWI3OTEgXHVhY2Y1XHVjOTAwXHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMTggblx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsIG5cdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCAyblx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWM3NDQgXHViMmY0XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmE4NVx1YzgxY1x1YjI5NCBcdWM4NzBcdWM4MWNcdWQ1MDQgXHViY2EwXHViOTc0XHVkMmI4XHViNzkxXHVjNzc0IDE4NDVcdWIxNDRcdWM1ZDAgXHVjZDk0XHVjZTIxXHVkNTg4XHVhY2UwLCBcdWQzMGNcdWQ1MDRcdWIyMDRcdWQyZjAgXHVjY2I0XHViZTQ0XHVjMWZjXHVkNTA0XHVhYzAwIDE4NTBcdWIxNDRcdWM1ZDAgXHVjOTlkXHViYTg1XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAsIDIwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMThjXHVjMjE4XHViMjk0IDRcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiAoMTEsIDEzLCAxNywgMTkpIFx1YjYxMCwgMTRcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCAyOFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YjI5NCAzXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gKDE3LDE5LCAyMyk8XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjNWYwXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAsIDJuXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMThjXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBuXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBuXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgMm5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAxMjMsNDU2PFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiI0OTQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hlYnlzaGV2J3MgVGhlb3JlbSIsImRlc2NyaXB0aW9uIjoiPHA+SWYgbiBpcyBhIHBvc2l0aXZlIGludGVnZXIsIHRoZXJlIGV4aXN0cyBhdCBsZWFzdCBvbmUgcHJpbWUgbnVtYmVyIGdyZWF0ZXIgdGhhbiBuIGFuZCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMm4uIFRoaXMgZmFjdCBpcyBrbm93biBhcyBDaGVieXNoZXYmIzM5O3MgdGhlb3JlbSBvciB0aGUgQmVydHJhbmQtQ2hlYnlzaGV2IHRoZW9yZW0sIHdoaWNoIGhhZCBiZWVuIGNvbmplY3R1cmVkIGJ5IEpvc2VwaCBMb3VpcyBGcmFuJmNjZWRpbDtvaXMgQmVydHJhbmQgKDE4MjImbmRhc2g7MTkwMCkgYW5kIHdhcyBwcm92ZW4gYnkgUGFmbnV0eSBMdm92aWNoIENoZWJ5c2hldiAoXHUwNDFmXHUwNDMwXHUwNDQ0XHUwNDNkXHUwNDQzXHUwNDQyXHUwNDM4XHUwNDM5IFx1MDQxYlx1MDQ0Y1x1MDQzMlx1MDQzZVx1MDQzMlx1MDQzOFx1MDQ0NyBcdTA0MjdcdTA0MzVcdTA0MzFcdTA0NGJcdTA0NDhcdTA0NTFcdTA0MzIsIDE4MjEmbmRhc2g7MTg5NCkgaW4gMTg1MC4gU3Jpbml2YXNhIEFpeWFuZ2FyIFJhbWFudWphbiAoMTg4NyZuZGFzaDsxOTIwKSBnYXZlIGFuIGVsZW1lbnRhcnkgcHJvb2YgaW4gaGlzIHBhcGVyIHB1Ymxpc2hlZCBpbiAxOTE5LiBQYXVsIEVyZFx1MDE1MXMgKDE5MTMmbmRhc2g7MTk5NikgZGlzY292ZXJlZCBhbm90aGVyIGVsZW1lbnRhcnkgcHJvb2YgaW4gMTkzMi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZXJlIGV4aXN0IDQgcHJpbWUgbnVtYmVycyBncmVhdGVyIHRoYW4gMTAgYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAyMCwgaS5lLiAxMSwgMTMsIDE3IGFuZCAxOS4gVGhlcmUgZXhpc3QgMyBwcmltZSBudW1iZXJzIGdyZWF0ZXIgdGhhbiAxNCBhbmQgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDI4LCBpLmUuIDE3LCAxOSBhbmQgMjMuPFwvcD5cclxuXHJcbjxwPllvdXIgbWlzc2lvbiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb3VudHMgdGhlIHByaW1lIG51bWJlcnMgZ3JlYXRlciB0aGFuIG4gYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAybiBmb3IgZWFjaCBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIG4uIFVzaW5nIHN1Y2ggYSBwcm9ncmFtLCB5b3UgY2FuIHZlcmlmeSBDaGVieXNoZXYmIzM5O3MgdGhlb3JlbSBmb3IgaW5kaXZpZHVhbCBwb3NpdGl2ZSBpbnRlZ2Vycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLiBBIGRhdGFzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuLiBZb3UgbWF5IGFzc3VtZSBuICZsZTsgMTIzNDU2LjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgemVyby4gSXQgaXMgbm90IGEgZGF0YXNldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBiZSBjb21wb3NlZCBvZiBhcyBtYW55IGxpbmVzIGFzIHRoZSBpbnB1dCBkYXRhc2V0cy4gRWFjaCBsaW5lIHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgYW5kIHNob3VsZCBuZXZlciBjb250YWluIGV4dHJhIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgaW50ZWdlciBjb3JyZXNwb25kaW5nIHRvIGEgZGF0YXNldCBjb25zaXN0aW5nIG9mIGFuIGludGVnZXIgbiBzaG91bGQgYmUgdGhlIG51bWJlciBvZiB0aGUgcHJpbWUgbnVtYmVycyBwIHNhdGlzZnlpbmcgbiAmbHQ7IHAgJmxlOyAybi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2011 Japan Domestic Contest A번