시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4063 2076 1823 52.627%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

10 7

예제 출력 1

9

힌트

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

W3sicHJvYmxlbV9pZCI6IjI5NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDBcdWI3N2NcdWQxYTBcdWMyYTRcdWQxNGNcdWIxMjRcdWMyYTRcdWM3NTggXHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZDBcdWI3N2NcdWQxYTBcdWMyYTRcdWQxNGNcdWIxMjRcdWMyYTRcdWM3NTggXHVjY2I0XHViMjk0IE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjMThjXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Mlx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjODAxXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NDRcdWM5YzEgXHVjOWMwXHVjNmIwXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMyMmJcdWM3OTAgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFBcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+UFx1Yjk3YyBcdWM5YzBcdWM2YjBcdWFjZTAsIFx1YzU0NFx1YzljMSBcdWM5YzBcdWM2YjBcdWM5YzAgXHVjNTRhXHVjNzQwIFBcdWM3NTggXHViYzMwXHVjMjE4XHViOTdjIFx1ZDA2Y1x1YWUzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOWMwXHVjNmI0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NDRcdWM5YzEgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM5YzBcdWM2YjBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViYTc0LCBcdWIyZTRcdWMyZGMgMlx1YmM4OCBcdWIyZThcdWFjYzRcdWI4NWMgXHVhYzA0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPk4sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgS1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2YjBcdWIyOTQgXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmx0OyBOLCBtYXgoMiwgSykmbmJzcDsmbHQ7IE4gJmxlOyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgS1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MiwgNCwgNiwgOCwgMTAsIDMsIDksIDUsIDcgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzljMFx1YzZjY1x1YzljNFx1YjJlNC4gN1x1YmM4OFx1YzlmOCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMjE4XHViMjk0IDlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUkVTRVRPIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc2lldmUgb2YgRXJhdG9zdGhlbmVzIGlzIGEgZmFtb3VzIGFsZ29yaXRobSB0byBmaW5kIGFsbCBwcmltZSBudW1iZXJzIHVwIHRvIE4uIFRoZSBhbGdvcml0aG0gaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+V3JpdGUgZG93biBhbGwgaW50ZWdlcnMgYmV0d2VlbiAyIGFuZCBOLCBpbmNsdXNpdmUuPFwvbGk+XHJcblx0PGxpPkZpbmQgdGhlIHNtYWxsZXN0IG51bWJlciBub3QgYWxyZWFkeSBjcm9zc2VkIG91dCBhbmQgY2FsbCBpdCBQOyBQIGlzIHByaW1lLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5Dcm9zcyBvdXQgUCBhbmQgYWxsIGl0cyBtdWx0aXBsZXMgdGhhdCBhcmVuJiMzOTt0IGFscmVhZHkgY3Jvc3NlZCBvdXQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIG5vdCBhbGwgbnVtYmVycyBoYXZlIGJlZW4gY3Jvc3NlZCBvdXQsIGdvIHRvIHN0ZXAgMi4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gTiBhbmQgSywgZmluZCB0aGUgSy10aCBpbnRlZ2VyIHRvIGJlIGNyb3NzZWQgb3V0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGludGVnZXJzIE4gYW5kIEsgKDEgJmxlOyBLICZsdDsgTiwgbWF4KDIsIEspJm5ic3A7Jmx0OyBOICZsZTsgMTAwMCkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgSy10aCBudW1iZXIgdG8gYmUgY3Jvc3NlZCBvdXQuPFwvcD5cclxuIiwiaGludCI6IjxwPndlIGNyb3NzIG91dCwgaW4gb3JkZXIsIHRoZSBudW1iZXJzIDIsIDQsIDYsIDgsIDEwLCAzLCA5LCA1IGFuZCA3LiBUaGUgc2V2ZW50aCBudW1iZXIgaXMgOS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: djm03178
  • 문제의 오타를 찾은 사람: moonhi123