[백준] 1929번 소수 구하기

문제링크 : 1929번 소수 구하기

에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 소수를 구할 범위만큼의 배열을 생성하고 그 안에서 합성수들을 찾아내 제거해나가는 식으로 구현할 수 있다.

코드

아래는 1부터 n까지의 수들이 소수인지 아닌지 판별하는 배열을 만드는 코드이다. i를 n의 제곱근까지만 검사하는 이유는 이전 글에 언급해두었다.

// 편하게 계산하기 위해서 0을 포함한 배열을 생성함
// 소수가 아니면 true, 맞으면 false 값이 들어아게 됨
boolean[] prime = new boolean[n + 1];

// 0과 1은 소수가 아님
prime[0] = true;
prime[1] = true;

for (int i = 2; i <= Math.sqrt(n); i++) {
	for (int j = i * 2; j <= n; j += i) {
		prime[j] = true;
	}
}

문제 풀이

코드

위의 소스 코드를 참고하여 문제에 적용시키면 다음과 같이 구현할 수 있다.

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

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

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        boolean[] prime = new boolean[n + 1];

        prime[0] = true;
        prime[1] = true;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            for (int j = i * 2; j <= n; j += i) {
                prime[j] = true;
            }
        }

        for (int k = m; k <= n; k++) {
            if (!prime[k]) {
                sb.append(k).append('\n');
            }
        }

        System.out.println(sb);
    }
}