[JAVA][Baekjoon] 1929번 소수 구하기 🌟🌟🌟

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

---

📌 접근 방식

1️⃣ 에라토스테네스의 체를 사용해 N까지의 소수를 구함.
2️⃣ 범위 M부터 N까지의 숫자 중 소수만 출력함.
3️⃣ 시간 효율성을 위해 i²부터 탐색하며 배수를 제거함.

---

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 1️⃣ 입력받기
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();  // 소수의 최소 범위
        int N = sc.nextInt();  // 소수의 최대 범위

        // 2️⃣ 소수를 체크할 배열 생성
        int[] A = new int[N + 1];  // 배열 크기를 N+1로 설정
        for (int i = 2; i <= N; i++) {  
            A[i] = i;  // 초기화: 각 인덱스에 자신의 값 저장
        }

        // 3️⃣ 에라토스테네스의 체로 소수 판별
        for (int i = 2; i <= Math.sqrt(N); i++) {  
            if (A[i] == 0) continue;  // 이미 지워진 수는 건너뜀
            for (int j = i + i; j <= N; j += i) {  // 배수 제거
                A[j] = 0;  // 소수가 아니면 0으로 표시
            }
        }

        // 4️⃣ M 이상 N 이하의 소수 출력
        for (int i = M; i <= N; i++) {  
            if (A[i] != 0) {  // 배열 값이 0이 아니면 소수
                System.out.println(A[i]);  // 소수 출력
            }
        }
    }
}

1️⃣ 배열 초기화

• A[i] = i: 배열에 자기 자신을 값으로 저장해 초기화.

2️⃣ 에라토스테네스의 체 적용

• i²부터 배수 제거: 중복 연산을 줄이기 위해 i * i부터 시작.
• 배수 제거: 소수가 아닌 수를 0으로 표시.

---

반응형

😊 느낀 점

에라토스테네스의 체를 이용하여 소수 문제를 풀어보았다💡 시간 복잡도 O(N log(log N)) 덕분에 1,000,000까지의 숫자에서도 빠르게 소수를 구할 수 있었다. 또한, i²부터 탐색하여 불필요한 연산을 줄이고, 효율적으로 구현할 수 있었다! 🚀