[백준 알고리즘] 1929 - 소수 구하기

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

1929번: 소수 구하기

 문제는 위와 같으며 에라토스테네스의 체를 통해 소수를 판별한 boolean 타입 배열을 먼저 구한 뒤, 주어진 m과 n 사이의 소수를 찾아 출력하는 문제입니다.

 

자바 코드는 다음과 같습니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 소수인 경우 true, 아닌 경우 false
        boolean[] primeNum = new boolean[1000001];
        Arrays.fill(primeNum, true);
        primeNum[0] = false; primeNum[1] = false;

        for (int i = 2; i * i < primeNum.length; i++) {
            for(int j = i * i; j < primeNum.length; j+=i) {  // i를 제외한 i의 배수를 구해 false로 변경
                primeNum[j] = false;
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        StringBuilder sb = new StringBuilder();
        // 입력 받은 m과 n 사이의 소수를 찾아 출력
        for (int i = m; i < n + 1; i++) {
            if (primeNum[i]) {
                sb.append(i).append("\n");
            }
        }

        System.out.print(sb);
    }
}