[1929] 소수 구하기 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

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

        int[] numbers = new int[N+1];
        for (int i = 2; i <= N; i++) {
            numbers[i] = i;
        }

        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (numbers[i] != 0) {
                for (int j = i+1; j < numbers.length; j++) {
                    if (numbers[j] != 0 && j % i == 0) {
                        numbers[j] = 0;
                    }
                }
            }
        }

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

        System.out.print(sb);
    }
}

 

numbers 배열에 2부터 N까지 저장한다.

 

소수인지 판별하기 위해 i를 2부터 N의 제곱근까지 순회하며 i의 배수를 제거한다.

N의 제곱근까지만 순회하는 이유는 N의 약수는 N의 제곱근보다 작으므로, N보다 작은 다른 수들의 약수도 N의 제곱근보다 작기 때문이다.

 

소수 판별이 끝나고 제거되지 않은 수들을 출력한다.