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

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

들어가며

오늘은 시간 복잡도를 고려하여 소수를 찾는 알고리즘은 에라토스테네스의 체와 관련 문항에 대해서 정리해보려 한다.

---

에라토스테네스의 체

에라토스테네스의 체 원리 - 이미지 출처(krapoi.tistory.com)

에라토스테네스의 체는 소수를 찾는 대표적인 알고리즘이다.

위 이미지는 에라토스테네스의 체의 원리를 잘 나타내고 있다.

원리

1. 2부터 소수를 구하고자 하는 구간(N, 위 이미지에서는 120)의 모든 수를 나열한다.(주로 N+1까지의 int 배열을 생성한다.)
2. 생성한 int 배열을 for문을 활용,  i = 2부터 i <= N까지 탐색하며 intArr[i]==0이면 i를 소수로 간주한다.
3. 이후 i부터 i의 배수들을 모두 지운다.(i를 배수로 갖으니 소수가 아니므로)
4. 이 과정을 i <= N까지 반복해준다.

 

위 원리를 활용하여 백준 2960번 문제, 에라토스테네스의 체를 풀이해보았다.

---

에라토스테네스의 체

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

7 3

예제 출력 1

6

예제 입력 2

15 12

예제 출력 2

7

예제 입력 3

10 7

예제 출력 3

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

Solution.java

package baekjoon;

import java.io.*;
import java.util.StringTokenizer;

/* 에라토스테네스의 체 */
// https://www.acmicpc.net/problem/2960
public class baekjoon2960 {
    public int solution(int N, int K) {
        int answer = 0;
        int cnt = 0;
        int[] intArr = new int[N + 1]; // 소수를 확인할 배열(에라토스테네스의 체)

        for (int i = 2; i <= N; i++) { // 0과 1은 소수가 아니니 제외하고 2부터 N까지 탐색
            if (intArr[i] == 0) { // 배열의 값이 0이라면 소수
                for (int j = i; j <= N; j += i) { // 해당 소수들의 배수를 탐색하며 값으로 1을 할당
                    if(intArr[j]!=1) {
                        cnt++;
                        intArr[j] = 1;
                        answer = j;
                        if (cnt == K) return answer;
                    }
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        baekjoon2960 T = new baekjoon2960();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 소수를 구할 범위 (N까지)
        int K = Integer.parseInt(st.nextToken()); // K번째
        bw.write(T.solution(N, K) + "\n");
        bw.flush();
        bw.close();
    }
}

---

Reference

백준 2920번 - 에라토스테네스의 체