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

문제

 

 

힌트

에라스토테네스의 체를 이용하여 푼다.

 

 

에라스토테네스의 체의 기본 원리

체로 치듯이 수를 걸러낸다 하여 '에라스토테네스의 체' 라고 부른다. 

1. n까지의 모든 수가 담긴 배열을 준비한다.
2. 모두 소수라고 가정한다.
3. 값을 반복하며 배수를 지운다.

 

 

문제 반례 찾는 법

아래 링크에서 확인할 수 있다.

https://skylarcoding.tistory.com/303

백준 알고리즘 문제 풀기, 반례 찾는 방법

 

 

 

 

 

 

문제풀이 

package AlgorithmStudy.src.silver;

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

public class S1929 {
    public static void main(String[] args) throws IOException {
        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());

        getPrime(m, n);
    }

    // 에라스토테네스의 체
    public static void getPrime(int m, int n) {
        boolean[] list = new boolean[n + 1];

        list[0] = true; // 소수가 아님
        list[1] = true;

        // 소수 찾기, 배수 체크
        for (int j = 2; j * j <= n ; j++) {  
            if (!list[j]) {
                for (int i = j * j; i <= n; i += j) {  
                    list[i] = true;
                }
            }
        }

        // 결과 출력
        for (int i = m ; i <= n ; i++) {
            if (!list[i]) {
                System.out.println(i);
            }
        }
    }
}

 

 

해설

1. 범위의 값을 boolean 배열로 만듦
2. 소수 찾으며, 배수를 체크한다.
       이때, 해당 값은 제외하고 배수부터 찾는다. 해당 값이 이전에 지워지지 않았다면 소수라 판단하기 때문.
       해당 값에 해당 값을 더해가며 배수를 삭제한다.
3. 소수 일때를 찾아 결과를 출력한다.

 

 

        // 소수 찾기, 배수 체크
        for (int j = 2; j * j <= n ; j++) {  // 최대값의 제곱근까지 돌며 아직 지워지지 않은 소수 찾기.
            if (!list[j]) { // j 값일 때 다른 수의 배수로서 지워지지 않았다면 j는 소수.
                // 이미 지워졌다면 앞선 값들의 배수이기 떄문에 패스 !
                for (int i = j * j; i <= n; i += j) {   // j의 배수 삭제 (j 배수 부터 시작, i 에 j를 더해가면서 배수 삭제)
                    list[i] = true;
                }
            }
        }

 

 

* 제곱근까지 도는 이유 

제곱근 이후는 이미 이전에 지워진 값들이기 때문에 그 이후의 것을 굳이 돌 필요가 없기 때문이다.