시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 7937 3629 3018 50.757%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

1
10
13
100
1000
10000
100000
0

예제 출력 1

1
4
3
21
135
1033
8392
W3sicHJvYmxlbV9pZCI6IjQ5NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYTBcdWI5NzRcdWQyYjhcdWI3OTEgXHVhY2Y1XHVjOTAwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHViY2EwXHViOTc0XHVkMmI4XHViNzkxIFx1YWNmNVx1YzkwMFx1Yzc0MCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IG5cdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjLCBuXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgMm5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyMThcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWIyOTQgXHViMGI0XHVjNmE5XHVjNzQ0IFx1YjJmNFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NCBcdWJhODVcdWM4MWNcdWIyOTQgXHVjODcwXHVjODFjXHVkNTA0IFx1YmNhMFx1Yjk3NFx1ZDJiOFx1Yjc5MVx1Yzc3NCAxODQ1XHViMTQ0XHVjNWQwIFx1Y2Q5NFx1Y2UyMVx1ZDU4OFx1YWNlMCwgXHVkMzBjXHVkNTA0XHViMjA0XHVkMmYwIFx1Y2NiNFx1YmU0NFx1YzFmY1x1ZDUwNFx1YWMwMCAxODUwXHViMTQ0XHVjNWQwIFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMTBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwLCAyMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YjI5NCA0XHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gKDExLCAxMywgMTcsIDE5KSBcdWI2MTAsIDE0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgMjhcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyMThcdWIyOTQgM1x1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuICgxNywxOSwgMjMpPFwvcD5cclxuXHJcbjxwPlxyXG5cdG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjZTAsIDJuXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMThjXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgblx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWJhNzAsIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKG4gJmxlOyAxMjM0NTYpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBuXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWNlMCwgMm5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hlYnlzaGV2J3MgVGhlb3JlbSIsImRlc2NyaXB0aW9uIjoiPHA+SWYgbiBpcyBhIHBvc2l0aXZlIGludGVnZXIsIHRoZXJlIGV4aXN0cyBhdCBsZWFzdCBvbmUgcHJpbWUgbnVtYmVyIGdyZWF0ZXIgdGhhbiBuIGFuZCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMm4uIFRoaXMgZmFjdCBpcyBrbm93biBhcyBDaGVieXNoZXYmIzM5O3MgdGhlb3JlbSBvciB0aGUgQmVydHJhbmQtQ2hlYnlzaGV2IHRoZW9yZW0sIHdoaWNoIGhhZCBiZWVuIGNvbmplY3R1cmVkIGJ5IEpvc2VwaCBMb3VpcyBGcmFuJmNjZWRpbDtvaXMgQmVydHJhbmQgKDE4MjImbmRhc2g7MTkwMCkgYW5kIHdhcyBwcm92ZW4gYnkgUGFmbnV0eSBMdm92aWNoIENoZWJ5c2hldiAoXHUwNDFmXHUwNDMwXHUwNDQ0XHUwNDNkXHUwNDQzXHUwNDQyXHUwNDM4XHUwNDM5IFx1MDQxYlx1MDQ0Y1x1MDQzMlx1MDQzZVx1MDQzMlx1MDQzOFx1MDQ0NyBcdTA0MjdcdTA0MzVcdTA0MzFcdTA0NGJcdTA0NDhcdTA0NTFcdTA0MzIsIDE4MjEmbmRhc2g7MTg5NCkgaW4gMTg1MC4gU3Jpbml2YXNhIEFpeWFuZ2FyIFJhbWFudWphbiAoMTg4NyZuZGFzaDsxOTIwKSBnYXZlIGFuIGVsZW1lbnRhcnkgcHJvb2YgaW4gaGlzIHBhcGVyIHB1Ymxpc2hlZCBpbiAxOTE5LiBQYXVsIEVyZFx1MDE1MXMgKDE5MTMmbmRhc2g7MTk5NikgZGlzY292ZXJlZCBhbm90aGVyIGVsZW1lbnRhcnkgcHJvb2YgaW4gMTkzMi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZXJlIGV4aXN0IDQgcHJpbWUgbnVtYmVycyBncmVhdGVyIHRoYW4gMTAgYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAyMCwgaS5lLiAxMSwgMTMsIDE3IGFuZCAxOS4gVGhlcmUgZXhpc3QgMyBwcmltZSBudW1iZXJzIGdyZWF0ZXIgdGhhbiAxNCBhbmQgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDI4LCBpLmUuIDE3LCAxOSBhbmQgMjMuPFwvcD5cclxuXHJcbjxwPllvdXIgbWlzc2lvbiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb3VudHMgdGhlIHByaW1lIG51bWJlcnMgZ3JlYXRlciB0aGFuIG4gYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAybiBmb3IgZWFjaCBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIG4uIFVzaW5nIHN1Y2ggYSBwcm9ncmFtLCB5b3UgY2FuIHZlcmlmeSBDaGVieXNoZXYmIzM5O3MgdGhlb3JlbSBmb3IgaW5kaXZpZHVhbCBwb3NpdGl2ZSBpbnRlZ2Vycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLiBBIGRhdGFzZXQgaXMgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuLiBZb3UgbWF5IGFzc3VtZSBuICZsZTsgMTIzNDU2LjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgemVyby4gSXQgaXMgbm90IGEgZGF0YXNldC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBiZSBjb21wb3NlZCBvZiBhcyBtYW55IGxpbmVzIGFzIHRoZSBpbnB1dCBkYXRhc2V0cy4gRWFjaCBsaW5lIHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgYW5kIHNob3VsZCBuZXZlciBjb250YWluIGV4dHJhIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBvdXRwdXQgaW50ZWdlciBjb3JyZXNwb25kaW5nIHRvIGEgZGF0YXNldCBjb25zaXN0aW5nIG9mIGFuIGludGVnZXIgbiBzaG91bGQgYmUgdGhlIG51bWJlciBvZiB0aGUgcHJpbWUgbnVtYmVycyBwIHNhdGlzZnlpbmcgbiAmbHQ7IHAgJmxlOyAybi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=