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

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

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

 

문제 조건

 

문제 이해하기

이 문제는 사실상 에라토스테네스의 체가 뭔지만 바로 풀 수 있는 문제이다.

에라토스테네스의 체는 문제 조건에서 나와있듯이, N보다 작거나 같은 모든 소수를 찾는 알고리즘이다.

알고리즘은 다음과 같다. 

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

알고리즘을 이해하기 위해, N을 7로 설정하여 예를 들어보자. 

1. 2부터 N(=7)까지 모든 정수를 적는다.
2 3 4 5 6 7

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=2)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 2, P = 2가 되며 이 수는 소수이다.

3. P(=2)를 지우고, 아직 지우지 않은 P(=2)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=2)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=2)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 2

2 3 4 5 6 7

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=3)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 3, P = 3이 되며 이 수는 소수이다.

3. P(=3)를 지우고, 아직 지우지 않은 P(=3)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=3)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=3)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 3

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=5)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 5, P = 5이 되며 이 수는 소수이다.

3. P(=5)를 지우고, 아직 지우지 않은 P(=5)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=5)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=5)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

-> 여기서 P = 5

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P(=5)라고 하고, 이 수는 소수이다.
2 3 4 5 6 7 <- 이 중 가장 작은 숫자는 7, P = 7이 되며 이 수는 소수이다.

3. P(=7)를 지우고, 아직 지우지 않은 P(=7)의 배수를 크기 순서대로 지운다.
2 3 4 5 6 7 <- P(=7)를 지우고,
2 3 4 5 6 7 <- 아직 지우지 않은 P(=7)의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
-> 모든 수를 지웠음!

-> 여기서 P = 7

지금까지 P의 값으로는 2, 3, 5, 7이 나왔다. 

이 알고리즘을 이용하면 쉽게 N 이하의 소수를 구할 수 있다!

 

하지만 위의 2960번 문제는 소수를 구하는 문제가 아니라,

N이 주어졌을 때, K번째로 지워지는 수를 구하는 문제이다.

 

그럼 알고리즘을 그대로 따라서 구현해보자!

 

문제 풀이 (코드)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	boolean[] prime = new boolean[n + 1];
    	
    	int count = 0;
    	for(int i = 2; i <= n; i++) {
    		for(int j = i; j <= n; j += i) {
    			if(prime[j] == false) {
        			count++;
        			prime[j] = true;
    			}

    			if(count == k) {
    				System.out.println(j);
    				System.exit(0);
    			}
    		}
    	}
    }
}