(백준)BOJ2960 - 에라토스테네스의 체

소수를 찾는 유명한 알고리즘인 에라토스테네스의 체이다.

 

에라토스테네스의 체란?

N보다 작거나 같은 모든 소수를 찾는 알고리즘이다.

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

ex) 소수인 2, 3, 5, 7, ... 의 배수를 지운다.

 

코드로 구현하면 아래와 같다.

public class Eratos {

    static boolean[] prime = new boolean[121];

    public static void main(String[] args) {
        int N = 120;

        // 소수는 false, 아니면 true
        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(N); i++) {
            // 소수가 아니면 다음으로 넘어감
            if (prime[i]) continue;
            // i의 배수 중 소수가 아닌것들을 찾아 true
            for (int j = i * i; j <= N; j += i) {
                prime[j] = true;
            }
        }

        // 소수 출력
        for (int i = 1; i <= N; i++) {
            if (!prime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

 

 

아래 백준 문제를 참고한다.

 

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

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

 

---

코드설명

N과 K를 입력받아, K번째로 지우는 수를 반환한다.

 

i가 2부터 N까지 반복하면서, i의 배수를 지우는 과정을 수행한다.

for (int i = 2; i <= N; i++) {
	for (int j = i; j <= N; j += i) {
    
    }
}

 

이때, 아직 지워지지 않은 수 중에서 가장 작은 수를 찾기위해 prime배열을 사용한다.

만약 j번째 수가 아직 지워지지 않았다면, count를 증가시키고 prime[j]를 true로 바꾼다.

count와 K가 같아지면 j를 반환하고 함수를 종료한다.

if (!prime[j]) {
	count++;
	prime[j] = true;
}
if (count == K) {
	return j;
}

 

만약 K번째로 지워지는 수를 찾지 못했다면, -1을 반환한다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2960 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        System.out.println(sieve(N, K));
    }

    // 에라토스테네스의 체 함수
    // K번째 지워지는 수를 찾아내는 함수
    public static int sieve(int N, int K) {
        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]) {
                    count++;
                    prime[j] = true;
                }
                if (count == K) {
                    return j;
                }
            }
        }
        return -1;
    }
}