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

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

2960번: 에라토스테네스의 체

 

 

 

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 cnt = 0;
        int answer = 0;
        int[] arr = new int[n+1];

        for(int i=2; i<=n; i++){
                for(int j=i; j<=n; j=j+i){
                    if(arr[j]==0){
                        cnt++;
                        arr[j] = 1;
                    }
                    if(cnt==k){
                        System.out.println(j);
                        System.exit(0);
                    }
                }
        }
    }
}

 

 

문제에 나와있는대로 구현하면 된다.

 

 

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

 

2부터 N까지 0으로 채워진 배열을 만든다.

P는 2부터 시작해 이중 for문을 돌며 P를 포함한 P의 배수들을 1로 바꾸고, cnt를 증가시킨다.

cnt가 입력받은 k와 같아질 때, 그 때 지우게된 숫자 j를 출력하고 시스템을 종료시킨다.