[백준] 2960번 - 에라토스테네스의 체 [Java]

https://www.acmicpc.net/problem/2960

 

[백준] 2960번 - 에라토스테네스의 체 [Java]

[백준] 2960번 - 에라토스테네스의 체 [Java]

---

1.  아이디어

 

에라토스테네스의 체의 구현 원리와 유사한 문제로 2중 for문을 통해 에라토스테네스의 체를 구현하는 로직을 약간 수정하면 해결할 수 있다.

---

2. 문제풀이

 

방문체크를 통해 중복 제거를 방지하고 order 변수로 K번째 여부를 파악하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean[] visited = new boolean[1 + N];
        int order = 0;

        out:
        for (int i = 2; i <= N; i++) {
            for (int j = i; j <= N; j += i) {
                if (visited[j]) continue;

                visited[j] = true;
                order++;
                if (order == K) {
                    System.out.println(j);
                    break out;
                }
            }
        }
    }
}

---

4. 후기