[Java]백준_1929 : 소수 구하기

Alal11·2023년 3월 24일

Java boj

출처

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

문제

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

입력

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

출력

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

예제 입출력

알고리즘 분류

수학
정수론
소수 판정
에라토스테네스의 체

➡️문제 분석

에라토스테네스의 체를 이용하여 소수를 구하는 문제이다.

➡️코드(⭕)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

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

        int[] arr = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
        for (int i = 2; i <= n; i++) {
            if (arr[i] == 0) continue;

            for (int j = i * 2; j <= n; j += i) {
                arr[j] = 0;
            }
        }
        for (int k = m; k <= n; k++) {
            if (arr[k] != 0)
                System.out.println(arr[k]);
        }
    }
}

➡️코드 분석

m과 n을 입력받고, 크기가 n+1인 배열 arr을 선언해준다.
arr 배열에 2부터 n까지의 수를 인덱스와 요소 값을 일치시켜 넣어준다.
소수는 2, 3, 5 ...이므로 이 수들의 배수는 모두 소수가 아니다.
따라서 i는 2부터 n까지 반복하는데 arr[i]이 0이면 소수가 아닌 것으로 처리되었으니까 continue로 넘어가준다.
j는 i*2부터 i씩 증가해준 값은 소수가 아니므로 해당 j 인덱스의 값은 0 처리를 해준다.
이렇게 해주면 소수인 arr[3]는 3, 소수가 아닌 arr[4]는 0으로 처리가 된다. 따라서 m부터 n까지의 인덱스 중에서 요소 값이 0이 아닌 것만 출력해주면 소수가 출력된다.