[백준] 1929 소수 구하기- Java

코딩테스트/알고리즘 문제

[백준] 1929 소수 구하기- Java

glorypang 2025. 3. 27. 10:00

728x90

SMALL

📌 문제 정보

출처: 문제 링크
난이도: ⭐
문제 유형: 수학
사용 언어: Java

🔍 문제 설명

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

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

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

💡 풀이 노트

💡 에라토스테네스의 체란?

고대 그리스의 수학자 에라토스테네스가 만든 방법으로, 소수를 빠르게 찾는 알고리즘

2부터 시작해 배수들을 지워나가며 소수만 남기는 방식.
시간 복잡도는 O($nlog⁡log⁡n$)으로 빠른 편

boolean[] num = new boolean[N+1];
Arrays.fill(num,true);

인덱스를 수로 사용하여, 소수인지 여부를 저장하는 배열
처음에는 모두 소수라고 가정( `true`)

num[0] = false;
num[1] = false;

`num[0]` ,`num[1]` 은소수가 아니므로 `false` 처리

for(int i =2 ;i <= Math.sqrt(N); i++){
	if(num[i]){
	for(int j = i*i ; j <= N ; j += i)
		num[j] = false;
	}
}

`i`의 배수들을 지워나가며 소수가 아닌 것들을 제거

🚀 코드 (Java)

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());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] num = new boolean[N+1];
        Arrays.fill(num,true);

        num[0] = false;
        num[1] = false;

        for(int i =2 ;i <= Math.sqrt(N); i++){
            if(num[i]){
                for(int j = i*i ; j <= N ; j += i)
                    num[j] = false;
            }
        }
        for(int i = M ;i <= N ;i++){
            if(num[i]){
                System.out.println(i);
            }
        }
    }
}