[백준] 2960번 : 에라토스테네스의 체 – JAVA [자바]

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

2960번: 에라토스테네스의 체

 

---

• 문제

 

 

---

• 문제 풀이

백준 2960번 에라토스테네스의 체는 실버 4 난이도의 수학, 구현 및 에라토스테네스의 체 문제이다. 이 문제에서는 정수 N과 K가 주어진다. 2부터 N까지 에라토스테네스의 체 알고리즘을 적용시킨다고 할 때 K번째로 지우는 수를 출력하면 된다.

 

참고로 원래 에라토스테네스의 체 알고리즘에서는 숫자의 배수만 지운다. 즉, 예를 들어서 2의 배수를 지울 때 2는 원래는 안 지우는데 이 문제에서는 2도 같이 지워야 한다.

 

만약에 에라토스테네스의 체에 대해서 잘 모른다면 밑에 있는 링크를 참고하면 좋겠다.

 

https://propercoding.tistory.com/182

[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes)

 

우선 n과 k를 입력받고 n까지 저장할 수 있는 배열 arr을 선언하고 초기화해준다. 그다음에 2부터 시작해서 2를 포함한 배수들을 차례대로 지워준다. 숫자 하나씩 지울 때마다 k를 1씩 감소시켜 주고 만약에 숫자를 지우고 나서 k가 0이 되면 그 지운 숫자가 정답이 된다. 

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

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());
        //n, k 입력 받기
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        primeNumber(n,k);
    }

	//에라토스테네스의 체 알고리즘
    static void primeNumber(int n, int k) {
        int[] arr = new int[n+1];  ////n까지 저장할 수 있는 배열 선언

        //배열 초기화화
       for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
        for (int i = 2; i <= n; i++) {
            if (arr[i] == 0) continue; //이미 지운 수는 건너뛰기

            //배수들 지우기
            for (int j = i; j <= n; j+=i) {
                if (arr[j] != 0) {
                    arr[j] = 0;
                    k--;
                    //k번째로 지운 수 출력
                    if (k == 0) {
                        System.out.print(j);
                        return;
                    }
                }
            }
        }
    }
}