BOJ 1929 소수 구하기 [Java]

BOJ 1929 소수 구하기

1. 문제 링크

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

2. 문제 해설

주어지는 두 수의 범위가 1부터 1,000,000 사이이다. 1부터 1,000,000까지 모두 나눠보는 방식은 시간 제한에 걸리기도 하고 굉장히 비효율적이다.
주어진 범위 내에서 소수 판별을 하는 가장 좋은 방법으로 '에라토스테네스의 체' 라는 방식이 있다.

예를 들어 1부터 100까지의 수 중에서 소수를 판별한다고 할 때, 에라토스테네스의 체가 어떻게 동작하는지 살펴보자.

1. 일단 소수도 합성수도 아닌 1을 제외한다.
2. 2를 제외한 범위 내의 2의 배수를 전부 제외한다.
3. 3을 제외한 범위 내의 3의 배수를 전부 제외한다.
4. 4의 배수는 이미 2의 배수를 제외하는 과정에서 제외되었으므로 생략 가능하다.
   그러므로 2와 3 다음의 가장 작은 소수 5를 제외한 범위 내의 5의 배수를 전부 제외한다.
   .
   .
   .

위 과정을 따라 배수들을 제거하여 마지막까지 남아 있는 수가 소수이다.
그렇다면 1~n까지의 소수를 알고 싶을 때, 1부터 n까지의 모든 수들의 배수를 제외해줘야 할까? 다행히도 그렇지 않다.
m = a x b (m < n)라고 할 때, a와 b 중 적어도 하나는 루트n 이하이다. 즉, n보다 작은 합성수 m은 루트m보다 작은 수의 배수들만 제외해줘도 전부 제거가 된다는 의미이다.
위의 예시 1부터 100까지의 소수를 알아보는 경우는 10의 배수까지만 제외해주면 모든 합성수가 제외된다.

코드에서도 위에서 설명한 에라토스테네스의 체를 이용하였다.true이면 소수, false이면 소수가 아님을 의미하는 isPrime 배열을 만들었다. 일단 isPrime 배열 전체를 true로 초기화 한 후, 위에서 설명한 것처럼 루트n 보다 작은 수들의 배수들을 전부 false 처리하였다.
m부터 n까지 순회하며 isPrime이 true인 수만 출력하였다.

3. 코드 보기

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

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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] = false;
        isPrime[1] = false;
        for (int i = 2; i < n + 1; i++)
            isPrime[i] = true;

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

        for (int i = m; i <= n; i++)
        {
            if (isPrime[i] == true)
                bw.write(Integer.toString(i) + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}