[백준 문제 풀이] 1929번 소수 구하기

Junu Kim·2026년 1월 3일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

83/89

[1929] 소수 구하기

난이도: ★★☆☆☆ • solved on: 2026-01-03

문제 요약

문제 유형: 수학, 에라토스테네스의 체, 구현
요구사항: 입력된 구간 [n, m] 안에 존재하는 모든 소수를 한 줄씩 출력해야 한다.

사용 개념

자료구조
- boolean[] : 합성수 여부 (표시 배열)
- StringBuilder : 출력 누적
알고리즘/기법
- 에라토스테네스의 체 (Sieve of Eratosthenes)
- 배수 마킹 (Marking multiples)
핵심 키워드
- 소수 (prime number)
- 합성수 (composite number)
- 배수 (multiple)

풀이 아이디어

문제 분해

0과 1은 소수가 아니므로 먼저 합성수 취급(true)로 표시한다.

2부터 시작해, 아직 체크되지 않은 수(소수 후보)를 만나면 그 수의 배수들을 합성수(true)로 표시한다.

최종적으로 arr[i] == false인 수만 출력한다(소수만 남김).
핵심 로직 흐름
arr[0] = arr[1] = true  // 소수 아님(합성수 취급)
for i = 2 .. m:
    if arr[i] == true: continue
    for j = 2 while i*j <= m:
        arr[i*j] = true  // 합성수 표시

for i = n .. m:
    if arr[i] == false: print i
예외 처리

0, 1은 소수가 아니므로 반드시 제외한다.

boolean 배열의 기본값이 false이므로, “표시되면 합성수(true)” 방식으로 관리한다.

코드

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

class Main {
    public static boolean[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        arr = new boolean[m+1];
        StringBuilder sb = new StringBuilder();
        makeSlieve();
        
        for(int i = n; i <= m; i++){
            if(!arr[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
    public static void makeSlieve(){
        arr[0] = true;
        arr[1] = true;
        for(int i = 2; i < arr.length; i++){
            if(arr[i]) continue;
            for(int j = 2; i*j < arr.length; j++){
                arr[i*j] = true;
            }
        }
    }
}