백준 1929번 : 소수 구하기 (에라토스테네스의 체)
이전의 문제도 마찬가지로 소수를 핸들링하는 문제였는데,
해당 문제는 특정 자연수를 입력 받아 다음으로 나오는 소수 중 가장 작은 소수를 찾는 문제였고, 브루트포스 알고리즘을 활용했기 때문에 특별히 적지 않았다.
그런데, 이번 문제는 M과 N 자연수를 입력 받아서 M이상 N이하의 소수를 모두 출력하는 문제였기 때문에 단순 브루트포스 알고리즘으로 풀어버리면 시간복잡도가 높고 굉장히 오래걸린다.
구한 소수를 전체 출력해야하기 때문에 숫자가 커지면 커질 수록 당연히 계산해야하는 양이 많아지고 그 만큼 오래걸리는 것이다.
우선 가장 먼저 풀었던 브루트포스 알고리즘은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
for (int i = m; i <= n; i++) {
if (isPrime(i)) {
System.out.println(i);
}
}
}
public static boolean isPrime(long x) {
if (x < 2) return false;
for (long i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
}
소스코드를 보면 알겠지만 소수를 찾는 함수인 isPrime을 작성 하고 소수로 판별 되면 하나씩 출력하는 방식이다.
당연한 얘기지만 빠른 출력을 구현하지 않았기 때문에 시간이 굉장히 오래걸린다.
여러 값을 출력해내는 문제이기 때문에 다음과 같이 StringBuilder를 사용하여 빠른 출력을 구현했다.
1
2
3
4
5
6
7
StringBuilder sb = new StringBuilder();
for (int i = m; i <= n; i++) {
if (isPrime(i)) {
sb.append(i).append('\n');
}
}
System.out.println(sb);
그런데 여전히 느리다.
빠른 출력을 구현했기에 시간이 절반 이상 줄어들었지만 핵심 알고리즘인 isPrime 함수에 특별한 변화가 없기 때문에 아직 최적화가 완전히 이루어졌다고 보기 어려웠다.
이제 핵심 알고리즘인 소수를 탐색하는 로직을 최적화하기 위해 어떤 방법이 있을까 찾아보았다.
조금만 검색해봐도 소수 알고리즘의 최적화된 알고리즘이 바로 나오는데, 그 이름은 에라토스테네스의 체이다.
다음의 블로그1과 블로그2 에서 해당 알고리즘을 참고했다.
이 에라토스테네스의 체는 프로그래밍 대회에서 소수 관련 문제를 핸들링할 때 많이 사용한다고 한다.
해당 알고리즘의 흐름은 다음과 같다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)
알고리즘의 구현 자체는 크게 어렵지 않다.
기본적으로 0부터 n까지 소수인지 판별할 boolean 타입의 배열을 생성하고 해당 배열을 순회하며, 소수 알고리즘을 사용해 소수인지 판단을 true or false로 처리해주기만 하면 된다.
어찌보면 탐색 알고리즘과 비슷한 느낌이 들기도 한다.
다시 코드를 보면
1
2
3
4
5
6
7
8
9
10
boolean[] isPrime = new boolean[n + 1];
isPrime[0] = isPrime[1] = true;
for(int i=2; i <= Math.sqrt(n); i++){
if(!isPrime[i]) {
for(int j = i * i; j <= n; j += i) {
isPrime[j] = true;
}
}
}
이런 식으로 기존 소수를 구하던 알고리즘에 boolean 타입의 배열을 추가적으로 사용한 모습이다.
n의 제곱근까지 반복하여 소수를 찾던 효율적인 알고리즘은 그대로 사용하되, 만약 prime[i]가 false면 i 이후의 i 배수가 약수로 i를 가지고 있는 것이므로 모두 false를 입력하고, prime[i]가 true라면 i는 이미 소수가 아니므로 i의 배수 역시 소수가 아닌 것이 된다.
어떤 풀이에서는 기본적으로 배열의 모든 값을 true로 초기화하고 직관적으로 소수 = true, 아니면 false 인 방식으로 풀었지만, 굳이 Array.fill 과 같은 추가적인 연산 과정 없이 그 반대로 생각해서 푸는 것이 시간소요가 더 적어 해당 방식으로 풀어냈다.
전체 코드를 보면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
boolean[] isPrime = new boolean[n + 1];
isPrime[0] = isPrime[1] = true;
for(int i=2; i <= Math.sqrt(n); i++){
if(!isPrime[i]) {
for(int j = i * i; j <= n; j += i) {
isPrime[j] = true;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = m; i <= n; i++) {
if (!isPrime[i]) sb.append(i).append('\n');
}
System.out.println(sb);
}
}
에라토스테네스의 체는 소수 알고리즘의 꽃이라고 생각한다.
기본적으로 이 알고리즘만 사용할 줄 알면 소수 관련 문제는 깔끔하고 효율적으로 풀어낼 수 있다.
사실 이번 소수 문제를 풀면서 처음 접했지만 크게 어려운 알고리즘은 아니기 때문에 뒤따라오는 문제들을 더 풀어보면 많이 익숙해질 것이다.
이 에라토스테네스의 체 문제들을 정답률이 상당히 낮은데, 이건 아마 이 알고리즘을 모르고 풀어서 시간 초과 때문에 틀린 경우가 많지 않았을까싶다.