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

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 입력 1

7 3

예제 출력 1

6

예제 입력 2

15 12

예제 출력 2

7

예제 입력 3

10 7

예제 출력 3

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

W3sicHJvYmxlbV9pZCI6IjI5NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDBcdWI3N2NcdWQxYTBcdWMyYTRcdWQxNGNcdWIxMjRcdWMyYTRcdWM3NTggXHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZDBcdWI3N2NcdWQxYTBcdWMyYTRcdWQxNGNcdWIxMjRcdWMyYTRcdWM3NTggXHVjY2I0XHViMjk0IE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjMThjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Mlx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjODAxXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NDRcdWM5YzEgXHVjOWMwXHVjNmIwXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMyMTggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFBcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+UFx1Yjk3YyBcdWM5YzBcdWM2YjBcdWFjZTAsIFx1YzU0NFx1YzljMSBcdWM5YzBcdWM2YjBcdWM5YzAgXHVjNTRhXHVjNzQwIFBcdWM3NTggXHViYzMwXHVjMjE4XHViOTdjIFx1ZDA2Y1x1YWUzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOWMwXHVjNmI0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NDRcdWM5YzEgXHViYWE4XHViNGUwIFx1YzIxOFx1Yjk3YyBcdWM5YzBcdWM2YjBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViYTc0LCBcdWIyZTRcdWMyZGMgMlx1YmM4OCBcdWIyZThcdWFjYzRcdWI4NWMgXHVhYzA0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPk4sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgS1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2YjBcdWIyOTQgXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmx0OyBOLCBtYXgoMSwgSykmbmJzcDsmbHQ7IE4gJmxlOyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+MiwgNCwgNiwgOCwgMTAsIDMsIDksIDUsIDcgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzljMFx1YzZjY1x1YzljNFx1YjJlNC4gN1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMjE4XHViMjk0IDlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJFU0VUTyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHNpZXZlIG9mIEVyYXRvc3RoZW5lcyBpcyBhIGZhbW91cyBhbGdvcml0aG0gdG8gZmluZCBhbGwgcHJpbWUgbnVtYmVycyB1cCB0byBOLiBUaGUgYWxnb3JpdGhtIGlzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPldyaXRlIGRvd24gYWxsIGludGVnZXJzIGJldHdlZW4gMiBhbmQgTiwgaW5jbHVzaXZlLjxcL2xpPlxyXG5cdDxsaT5GaW5kIHRoZSBzbWFsbGVzdCBudW1iZXIgbm90IGFscmVhZHkgY3Jvc3NlZCBvdXQgYW5kIGNhbGwgaXQgUDsgUCBpcyBwcmltZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Q3Jvc3Mgb3V0IFAgYW5kIGFsbCBpdHMgbXVsdGlwbGVzIHRoYXQgYXJlbiYjMzk7dCBhbHJlYWR5IGNyb3NzZWQgb3V0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiBub3QgYWxsIG51bWJlcnMgaGF2ZSBiZWVuIGNyb3NzZWQgb3V0LCBnbyB0byBzdGVwIDIuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIE4gYW5kIEssIGZpbmQgdGhlIEstdGggaW50ZWdlciB0byBiZSBjcm9zc2VkIG91dC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnRlZ2VycyBOIGFuZCBLICgxICZsZTsgSyAmbHQ7IE4sIG1heCgxLCBLKSZuYnNwOyZsdDsgTiAmbGU7IDEwMDApLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIEstdGggbnVtYmVyIHRvIGJlIGNyb3NzZWQgb3V0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgdGhpcmQgZXhhbXBsZSwgd2UgY3Jvc3Mgb3V0LCBpbiBvcmRlciwgdGhlIG51bWJlcnMgMiwgNCwgNiwgOCwgMTAsIDMsIDksIDUgYW5kIDcuIFRoZSBzZXZlbnRoIG51bWJlciBpcyA5LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 2번