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

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

1929번: 소수 구하기

 

[접근] 

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하는 문제이다. 수의 범위가 주어졌기때문에 '에라토스테네스의 체'의 소수 구하는 방법을 이용하여 코드를 작성하였다. 

 

https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위 사이트를 참고 한다면 쉽게 이해 할 수 있을 것이다!

 

[코드]

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

//소수 구하기
//에라토스테네스의 체
public class Main1929 {
    public static void main(String[] args) throws IOException {


        BufferedReader br = new  BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        boolean []checkArray = erathosthenes(N);


        for (int i = M ; i<=N;i++){
            if(!checkArray[i]){
                sb.append(i).append("\n");
            }
        }


      System.out.print(sb);


    }

    public static boolean[] erathosthenes(int N){
        boolean[] checkArray = new boolean[N + 1];
        //소수 = false ; 소수가 아닌 숫자 = true;
        checkArray[0] = true;
        checkArray[1] = true;


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

        return checkArray;
    }
}