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

백준 6588번 골드바흐의 추측을 풀기 위한 단계1

에라토스테네스의 체

소수 판별 알고리즘

 

문제

 

문제는 소수를 찾는게 아니라

소수를 찾는 과정에서 지워지는 숫자중 특정 순번의 숫자를 찾는것.

 

입력되는 N값만큼의 배열을 만들고,

2부터 시작 하는 FOR LOOP를 돌린다. (문제에 2부터 시작이라고 제시되어있음)

 

2일 때 2, 4, 6... 배수의 크기 순서대로 지워주는데 지우는 작업을 위의 배열에 값을 true로 입력하는 작업으로 대체한다.

이미 지낫으면 skip

 

지나간 숫자는 값을 true로 입력 + count를 더해줘서 순번을 작성한다

그 후 count값이 입력받은 K와 일치하는지 체크하여 일치하면 break 후 출력한다.

 

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

public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        int max = Integer.parseInt(input[0]);
        int targetNum = Integer.parseInt(input[1]);
        int cnt = 0;

        boolean[] arr = new boolean[max+1];

        int ans = 0;
        for(int i=2; i<= max; i++){
           for(int j = i; j<=max; j+=i){
               if(!arr[j]){
                   cnt++;
                   arr[j] = true;
               }
               if(cnt == targetNum){
                   ans = j;
                   break;
               }
           }
           if(ans != 0) break;
        }
        System.out.println(ans);
    }
}

함수를 따로 만들어서 return 했으면 조금 더 깔끔해졋겟지만.. 귀찮은 관계로 그냥 break 처리