[BOJ][C++] 백준 2960번 에라토스테네스의 체
Updated:
2960 소수
1. 문제 정보
백준 온라인 저지 [2960번 에라토스테네스의 체] 문제의 링크입니다.
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
예제 입력1
10 7
예제 출력1
9
시간 / 메모리 제한
1초 / 128MB
2. 생각
- 문제 1929번 소수 구하기 문제와 비슷한 문제였습니다. 문제 1929번은 에라토스테네스의 체 방법으로 빠르게 배열에 소수가 무엇인지 남겨놓았고 그 소수를 활용하는 문제였습니다. 그러나 이 문제 2960번은 에라토스테네스가 어떻게 동작하는지, 어떤 순서로 수가 지워지는지에 관한 문제입니다.
-
문제에서 주어진 알고리즘을 따라하면 됩니다. 먼저, 2부터 N까지 모든 정수를 적습니다. prime 배열을 사용하였고, 이 문제에서는 소수도 지워집니다.
-
i를 2부터 시작하여 배수를 차례로 지웁니다. 지울때는 cnt 변수를 증가시켜 몇 개를 지웠는지 체크합니다. 이 cnt 변수가 k와 같아지는 순간이 k번째 지워진 수 입니다.
-
prime[j] = 0으로 만들며 지웁니다. 이미 prime[j]가 0이라면 이미 지운 것이기 때문에 넘어가야합니다.
- 이 문제는 소수도 지우므로 i와 j는 모두 n까지 증가시켜야합니다. n이 주어진다면 k의 최대 값은 k-1입니다.
Plus 참고. 지워지는 순서.
21번째36번째42번째58637984971052 - 4 - 6 - 8 - 10 -3 - 9 - 5 - 7
3. 소스코드 (C++)
