백준(baekjoon) [JAVA] - 1929번: 소수 구하기

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

1929번: 소수 구하기

---

import java.io.*;

// 소수 구하기
public class _1929 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int m = Integer.parseInt(input[0]);
        int n = Integer.parseInt(input[1]);

        boolean[] arr = new boolean[n + 1];
        arr[0] = arr[1] = true;
        for (int i = 2; i * i <= n; i++) {
            // 소수인 경우 --> 해당 수의 배수를 모두 체크(소수가 아님)
            if (!arr[i]) {
                for (int j = i * i; j <= n; j += i) {
                    arr[j] = true;
                }
            }
        }

        for (int i = m; i <= n; i++) {
            if (!arr[i]) {
                bw.write(i + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
}

---

MEMO

-- 에라토스테네스의 체를 이용하여 소수 판별

-- 기본적인 소수 판별(2부터 시작하여 나누어 떨어지는지 순차적으로 확인)방법은 시간초과

 

!! 좋은 개념들을 잘 숙지하기 !!