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

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)

출력

 

첫째 줄에 K번째 지워진 수를 출력한다.

 

 

알고리즘 설계

1. 일단 크기가 n+1인 배열을 만들어 2부터 n+1까지의 수를 입력한다

2. 삭제한 수를 0으로 만든다 

3. 이미 삭제한 수라면 pass하고 다음수를 check한다  

 

point.

삭제하면 count값을 하나 증가시켜서 count값이 k값과 같아지면

삭제한 해당 수를 출력하면 된다 

(이 후에 숫자는 볼필요 없는 문제이다)

 

import java.util.*;
public class Main {
    public static  void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int []number=new int[n+1];
        int count=0;
        for(int i=2;i<=n;i++){
            number[i]=i; //2부터 n까지 모든 정수를 적는다
        }

        for(int i=2;i<=n;i++) {
            for (int j = i; j <= n; j+=i) {
                if (number[j]>0) { //0보다 크다는건 아직 안지워졌다는거다
                    number[j] = 0; //아직 지우지 않은 수 중 가장 작은수 p를 지운다
                    count++;
                    if (count == k) {
                      System.out.print(j);
                    }
                }else if(number[j] == 0) { //이미 지워져있는 수라면 pass
                    continue;
                }

            }
        }

    }
}