백준 15965 K번째 소수(Java)

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

15965번: K번째 소수

ㅂ

---

 

해석 및 팁

 

---

 

50만 번째 소수를 구하려면 범위가 10000000은 잡아야 구할 수 있습니다. 따라서 에라토스테네스의 채를 통해 먼저 소수를 구해놓고 반복문을 통해 k번째 소수를 구하면 되는 문제입니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    boolean[] arr= new boolean[10000001];

    arr[0] = true;
    arr[1] = true;
    for(int i = 2; i * i <= 10000000; i++) {
      if(arr[i] == true) continue;
      for(int j = i * i; j <= 10000000; j += i) arr[j] = true;
    }

    int k = sc.nextInt();
    int count = 1;

    for(int i = 2; i <= 10000000; i++) {
      if(arr[i] == false) {
        if(count == k) {
        System.out.println(i);
        break;
        }
        count++;
      }
    }
    
  }
}