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

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 1929 소수 구하기

오늘문제는 M이상 N 이하의 모든 소수를 오름차순으로 출력하는 문제입니다.

M,N은 1이상 1,000,000 이하의 정수이고, M <= N을 만족합니다.

 

📘 문제

 

💡 해결 방법

M부터 N까지 모든 수를 돌면서 소수인지 판별합니다.

isPrime() 함수를 이용해 √n까지만 검사해서 효율적으로 처리합니다.

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

• 입력으로부터 M과 N을 읽어옵니다.
• M부터 N까지 반복하면 isPrime(i)가 true인 수 (즉, 소수)를 StringBuilder에 추가하여 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        
        StringBuilder sb = new StringBuilder();
        for (int i = m; i <= n; i++) {
            if (isPrime(i)) {
                sb.append(i).append("\n");
            }
        }
        
        System.out.print(sb);
        br.close();
    }
    
    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

 

이 문제는 소수 판별만 알면 어렵지 않지만 범위가 최대 1,000,000까지라서 효율적인 구현이 필요합니다.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)