[백준] 소수 구하기 (자바)

백준 소수 구하기 문제

문제풀이

이 문제는 소수 구하기 문제입니다
소수 구하기 문제는 단순한 이중 반복문을 통해서 해결할 수도 있지만 가끔씩 시간 초과가 발생하는 문제가 있습니다.
그런 문제를 해결하기 위해 고안된 방법이 에라토스테네스의 체입니다.

에라토스트네스의 체는 소수가 되는 배수의 수를 지워버리는 방법입니다.
소수는 특정 수를 곱하게 되면 그 수는 소수가 아니게 되어버리기 때문입니다.
따라서 문제에서 주어지는 범위까지 배열을 미리 만들어놓고 소수의 배수를 찾아서 true 처리를 합니다. true 처리가 되어있는 수는 소수 판단을 하지 않아서 평범한 이중 반복문을 사용하여 소수를 찾는 방법보다 훨씬 빠른 속도로 문제를 해결할 수 있습니다.
참고로 에라토스테네스의 체는 O(nlog(logn))의 시간복잡도를 가집니다.

이 문제는 에라토스테네스의 체 방식으로 해결했습니다.

구현코드

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

import java.lang.*;

public class Main{

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int numStart = Integer.parseInt(st.nextToken());
        int numEnd = Integer.parseInt(st.nextToken());

        boolean[] arr = new boolean[numEnd+1];
        arr[0] = arr[1] = true;

        for(int j =2; j<=Math.sqrt(numEnd); j++) {
            if (arr[j] == false){
                for (int k = j*j; k<=numEnd; k+=j){
                    arr[k] =true;
                }
            }

        }

        for (int i = numStart; i<=numEnd; i++){

            if (arr[i] == false){
                bw.write(i+"\n");
            }

        }

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

}

소수를 찾아야 하는 문제를 만나게 되면 웬만하면 에라토스테네스의 체 방식을 사용하는 것이 좋을 것 같습니다.