[백준] 1929번 소수 구하기 - Java[에라토스테네스의 체]

[백준] 1929번 소수 구하기 - Java[에라토스테네스의 체]

 

문제 출처

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

1929번: 소수 구하기

 

---

※ 풀이

범위내에 있는 수들 중에 소수만 고르는 문제이다.

하나의 수만 소수인지 아닌지 판별하는 경우에는 다른 방법을 쓸 수도 있지만 

이렇게 범위내의 모든 소수를 골라야 하는 경우에는 에라토스테네스의 체라는 방법을 사용한다.

• [에라토스테네스의 체 풀이]

1. N 까지의 범위를 가지는 배열을 만든다.

(해당 index 의 수가 소수인지 아닌지 판별해주는 역할)

 

2. 제일 작은 소수인 2부터 아래 과정을 돌린다.

2-1) 현재 지워지지 않은 수 x 를 중심으로 x를 제외한 x의 배수들은 모두 소수가 아니므로 배열에서 지운다.

-> x 가 이미 지워져있다면 바로 x+1로 넘어간다.

2-2) 다음 수 x+1 로 넘어가서 2-1을 반복한다.

 

이렇게 배열의 끝까지 반복문을 돌린 뒤 아직 지워지지 않은 수가 소수라고 보면 된다.

 

---

※ 소스코드

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

public class Main {

    static boolean[] isNotPrime = new boolean[1000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");
        int m = Integer.parseInt(split[0]);
        int n = Integer.parseInt(split[1]);

        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                erase(i, n);
            }
        }

        for (int i = m; i <= n; i++) {
            if (!isNotPrime[i] && i > 1) {
                System.out.println(i);
            }
        }
    }

    //number 를 제외한 수들을 지운다.
    static void erase(int number, int max) {
        int length = max / number;
        for (int i = 2; i <= length; i++) {
            isNotPrime[number * i] = true;
        }
    }
}