[백준] 1929번 : 소수 구하기 - JAVA

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

풀이

이전 글에서 사용했던 제곱근을 이용한 풀이는 시간 초과가 발생했다.

따라서 수학 공식인 에라토스테네스의 체를 이용한 풀이를 작성했다.

 

에라토스테네스의 체

가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법이다.

2부터 시작해서 특정 수의 배수를 모두 지운다.(자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    public static boolean[] decimal;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        decimal = new boolean[N + 1];
        isDecimal();
        for(int i = M; i < decimal.length; i++) {
            if(!decimal[i]) {
                System.out.println(i);
            }
        }
    }
    public static void isDecimal() {
        decimal[0] = decimal[1] = true;

        for(int i = 2; i <= Math.sqrt(decimal.length); i++) {
            if(decimal[i]) continue;
            for(int j = i * i; j < decimal.length; j += i) {
                decimal[j] = true;
            }
        }
    }
}

isDecimal 메서드가 에라토스테네스의 체이다.

N까지 범위의 배열을 생성하고, 2부터 N까지 각 수의 배수는 true값을 대입한다.(자기 자신을 제외한다.)

2 => 4, 6, 8, 10, 12 ...

3 => 9, 12, 15, 18 ...

4 => 16, 20, 24 ...

이때 i*i가 시작점인 이유는 이미 이전 수의 배수들에서 지워진 수이므로 굳이 탐색하지 않아도 되기 때문이다.

4를 예시로 든다면 4 * 2는 이미 2의 증가값에서 탐색한 값이고, 4 * 3 또한 3의 증가값에서 탐색한 값이므로 탐색하지 않는다.

 

* 문의사항이나 피드백은 언제나 환영입니다.