[JAVA] 백준 1929 에라토스테네스의 체

 

 

 

1929번: 소수 구하기

문제

M이상 M이하의 소수를 모두 출력하시오.

풀이

에라토스테네스의 체를 이용하여 소수를 구했습니다.’

에라토스테네스의 체

        for(int i=2; i<Math.sqrt(N); i++){
            int index = 2;
            while (true) {
                int now = index++ * i;

                if(now >= N) break;
                if(!A[now]) A[now] = true;
            }
        }

에라토스테네스의 체는 2~ $\sqrt{N}$까지의 모든 곱을 구하여 구해진다면 해당 숫자를 날려 구간의 소수를 모두 구할 수 있습니다.

출력

        StringBuilder sb = new StringBuilder();
        for(int i= M > 1 ? M : 2 ; i<N; i++){
            if(!A[i]){
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);

M이 1인 경우라면 1을 제외시켜야하기 때문에 2를 출력하고 2이상이라면 2부터 출력하도록 했습니다.

전체 코드

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

class Main {
    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())+1;

        boolean[] A = new boolean[N];

        for(int i=2; i<Math.sqrt(N); i++){
            int index = 2;
            while (true) {
                int now = index++ * i;

                if(now >= N) break;
                if(!A[now]) A[now] = true;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i= M > 1 ? M : 2 ; i<N; i++){
            if(!A[i]){
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);

    }

}

결과