[JAVA] 백준 1929번 소수 구하기

문제

 

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

 

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

입력예제

 

3 16

 

출력예제

 

3
5
7
11
13

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // n 크기의 boolean 배열을 만듦
        boolean[] prime = new boolean[n + 1];

        // 우선 모두 true로 채우기 (1은 소수이므로 false)
        for (int i = 2; i <= n; i++) {
            prime[i] = true;
        }

        // n보다 같거나 작을 때 까지 for문 돌리기
        for (int i = 2; i * i <= n; i++) {
            // i의 배수인 숫자를 false로 바꾸기
            for (int j = i + i; j <= n; j += i) {
                prime[j] = false;
                // 소수가 아닌 숫자는 전부 false가 됨
            }
        }

        // true인 숫자들은 전부 소수.
        // m부터 n의 범위까지 true인 숫자만 출력
        for (int i = m; i <= n; i++) {
            if (prime[i] == true) {
                bw.write(String.valueOf(i) + "\n");
            }
        }
        bw.flush();
        bw.close();
    }
}

 

 

 

에라토스테네스의 체 참고 글 

[알고리즘/JAVA] 에라토스테네스의 체

 

 

 

1929번: 소수 구하기