백준 2960 에라토스네테스의 체

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Sieve_of_Eratosthenes {
    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());
        int[] list = new int[N+1];
        for (int i = 2; i <= N; i++) {
            list[i] = i;
        }
        int cnt = 0;
        for(int i = 2; i<=N; i++){
            int count = 0;
            for(int j = 2; j<i; j++){
                if(i/j==0){
                    count++;
                    break;
                }
            }
            if(count==0){
                for(int k = 1; i*k <= N;k++){
                    if(list[i*k]!=0){
                        cnt++;
                        if(cnt == K){
                            System.out.println(list[i*k]);
                            return;
                        }
                        list[i*k] = 0;
                    }


                }
            }

        }
    }
}

풀이방법

1. 2부터 N까지 배열에 담는다.
2. 2부터 하나씩 소수인지 판별한다. 소수 인지는 자신보다 작은수로 다 나눠보는것으로 확인할 수 있다. 하나라도 나눠지는게 없다면 소수라고 판단한다.따라서 여기서 2중 포문을 사용하면 된다.
3. 소수일때 list에 자신의 배수에 해당하는 수를 다 지운다. (0으로 표기)그 후 cnt를 통해 몇번째 지워지는지 체크한다. 이때 이미 지워진 수도 확인하므로, 0이 아닐때만 cnt값을 증가시킨다.
4. cnt값과 K가 같다면 그때 지워지는 수를 출력한다.

후기

아니 나 이거 틀리게 제출했는데 맞다고 나왔다. 하지만 귀찮으니 이의제기는 안해야지.
그리고 2도 소수다. 초등학생도 아는거라고 하지만, 나도 초등학생때는 알았다. 까먹지말자

소수문제 나올때 한번 생각해 볼 것중에 어떤수가 소수인지 확인할때 2부터 그 수의 제곱근까지만 확인하면 소수판별이 가능하다. 개꿀팁이니 까먹지 말자
ex) 25는 5까지만, 41은 6까지만 확인해보면 소수인지 판별가능