문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
예제 입력
15 12
예제 출력
7
내가 했던 풀이 방법
-
boolean 배열인 Eratosthenes를 만든다. 이 배열의 모든 값을 true로 초기화한다. 이 배열은 false일 경우 지워진 수를 의미한다. 배열의 index는 0부터 시작하므로, Eratosthenes[0]은 숫자 1의 정보를 가지고 있다. 단, 숫자 1은 필요없으므로, 모든 배열은 index 1부터 탐색한다.
-
count가 K이상이 될 때까지 while문을 돌린다. while문 시작에 getP 함수를 이용하여 지우지 않은 수 중 가장 작은 수를 찾는다. (1부터 N까지 Eratosthenes 배열을 탐색하고, 첫번째로 true인 값을 찾으면 +1을 한 뒤 return한다. +1을 하는 이유는 배열의 index를 반환하는 것이 아닌 P 즉, 값을 반환하기 때문이다.)
-
1부터 N까지 반복문을 돌면서 현재 지워지지 않았으면서, 그 값이 P로 나누었을 때 나머지가 0일 경우(P의 배수) 해당 값의 배열을 false로 바꾸고 count를 1 증가시킨다. 또, answer 변수(n번째로 지워진 수)에 index+1을 한 값을 저장한다. (index가 아닌 값을 저장해야 하므로, +1) 만약 반복문이 끝나기 전에 count가 K가 됐을 경우, 즉시 반복문을 탈출한다.
-
while문을 탈출했으면 answer에 들어있는 값을 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N;
static boolean[] Eratosthenes;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
Eratosthenes = new boolean[N];
Arrays.fill(Eratosthenes, true);
int P;
int count = 0;
int answer = 0;
while (true) {
if(count>=K) break;
P = getP();
for(int i=1; i<N; i++) {
if(Eratosthenes[i] && ((i+1)%P==0)) {
Eratosthenes[i] = false;
count++;
answer = i+1;
}
if(count==K) break;
}
}
System.out.print(answer);
}
public static int getP() {
int result=0;
for(int i=1; i<N; i++) {
if(Eratosthenes[i]) {
result = i;
break;
}
}
return result+1;
}
}
회고
문제에서 주어진대로 구현했는데 계속 반복문에서 탈출 못하길래 이것저것 수정하니 해결된 문제.. 처음에는 왜 되는거지? 싶었는데, 정리하다보니 틀린 이유는 알았다. 처음에 getP에서 P를 찾을 때 바로 배열에 false를 시켜주었는데, count가 안 됐었다. (근데 왜 무한반복했을까나... 이건 좀 모르겠다.) 그래서 getP에서는 P만 찾고 지우지 않고, while문에서 지워주는 걸로 수정하니 정답이 됐다. 어떻게 무한 반복에서 탈출했는지는 잘 모르겠지만... 그래도 알고리즘 자체가 틀렸다는 게 아니라 좀 다행이었다. 이것도 못 풀었으면 자괴감이 들었을 듯..
