[JAVA] 소수 구하기 - 에라토스테네스의 체

백준 1929번 - 소수 구하기

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

 

개요

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

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

---

접근

에라토스테네스의 체 알고리즘을 사용해 문제를 작성하였다.

 

에라토스테네스의 체 알고리즘이란?

가장 작은 소수인 2부터, 2의 배수를 모두 소거, 

3을 제외한 3의 배수를 모두 소거,

4는 2의 배수로 제거 됐기 때문에 넘어감.

5를 제외한 5의 배수를 모두 소거,

 

이렇게 제거되지 않은 수의 배수를 소거해가며 주어진 범위의 소수를 구하는 방법이다.

 

 

예) 에라토스테네스의 체로 1~50까지의 범위에서 소수를 구하기

(1은 합성수나 소수가 아니기 때문에 제거후 시작)

 

2를 제외한 2의 배수 모두 소거.

 

3을 제외한 3의 배수 모두 소거.

 

5를 제외한 5의 배수 모두 소거.

 

7을 제외한 7의 배수 모두 소거.

 

결과

11부턴 판별할 필요가 없다.

• 2~10까진 판별이 완료 돼 소거됐기 때문에 , 11X11부터 판별해야 하는데, 이미 범위를 벗어나게 됨.

결국 탐색 범위의 제곱근까지만 연산하면 된다.

• 1X50 = 50
• 2X25 = 50
• 5X10 = 50
• 10X5 = 50
• 25X2 = 50
• 50X1 = 50

이렇게 가운데 약수를 기준으로 수가 중복되기 때문에, 제곱근(가운데) 까지만 확인하면 된다.

50의 제곱근은 약 7.07이므로, 7까지만 연산하면 됨.

---

코드

import java.io.*;
import java.util.*;
public class Solve1929 {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String [] input = br.readLine().split(" ");
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);

        boolean [] isPrime = new boolean[N+1]; //소수인지 아닌지 판별할 배열 true=소수, false=소수x
        Arrays.fill(isPrime, true); //모든 수를 true로 초기화 후, 소수가 아니면 배제하기 위함.
        isPrime[0] = false;
        isPrime[1] = false;

        int judgeNum = (int)Math.sqrt(N); //N의 제곱근까지만 검사해도 됨.(그 이후엔 수식이 대칭되기 때문)

        for(int i = 2; i <= judgeNum; i++) { //2부터 N의 제곱근까지 탐색
            if (isPrime[i]) { //소수라면?
                for (int j = i * i; j <= N; j += i) { //중복을 최소화하기 위해, 소수의 제곱값부터 그 값을 더해가며 제거
                    isPrime[j] = false;
                }
            }
        }
        //주어진 값 범위의 소수만 출력
        for(int i = M; i <= N; i++){
            if(isPrime[i])
                bw.write(i + "\n");
        }
        bw.flush();
        bw.close();
    }
}