[백준] 15965번 : K번째 소수 – JAVA [자바]

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

15965번: K번째 소수

 

---

• 문제

 

 

---

• 문제 풀이

백준 15965번 K번째 소수는 실버 2 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제는 추가로 부산일과학고 BSIS배 Code Festival에서 D번 문제로 출제된 문제이기도 하다. 이 문제 자체는 간단하다. 문제에서 입력으로 자연수 K가 주어지는데 K번째 소수를 출력하기만 하면 된다. 

 

이 문제는 에라토스테네스의 체를 이용해서 풀 수 있다. 아직 에라토스테네스의 체에 대해서 잘 모르면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/182

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

 

우선 이 문제에서는 k번째 소수를 구해야 한다. 그리고 k의 범위는 1부터 50만까지이다. 즉, 크기가 큰 배열을 선언해야 한다는 것이다. 그래서 우선 배열의 크기를 10,000,000으로 정하고 선언하고 초기화를 해준다. 

 

그다음에 2부터 시작해서 n까지 i의 배수들을 배열에서 지워준다. 이것은 배열에서 초기화를 해준 값을 0으로 바꿔주면 된다. 이렇게 하면 배열에 남아있는 값들은 모두 소수이다. 즉, 소수만 배열에 남는다는 것이다. 

 

이제 여기 배열에서 for-loop을 돌려 K번째 소수를 출력해주면 된다.

 

자세한 코드는 밑에 있는 코드를 참고해주면 되겠다.

 

---

• 코드

 

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));
        int k = Integer.parseInt(br.readLine());
        primeNumber(k);
    }

    //에라토스테네스의 체 메서드
    static void primeNumber(int k) {
        int[] arr = new int[10000001];  //k의 범위 50만까지여서 배열은 크게 선언
        int n = 10000000;
        //배열 초기화
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }

        //2부터 시작해서 i의 배수들을 배열에서 지워준다
        for (int i = 2; i <= n; i++) {
            //이미 지워진 수는 건너뛴다
            if (arr[i] == 0) continue;
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }

        int count = 1;
        
        //k번째 소수 출력하기
        for (int i = 2; i <= n; i++) {
            if (arr[i] != 0) {
                if (count == k) {
                    System.out.print(i);
                    break;
                }
                count++;
            }
        }
    }
}