백준 1929번 [소수 구하기](C++)-yes6686- 티스토리

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

---

문제 링크: https://www.acmicpc.net/problem/1929

문제 설명:

자연수 M과 N이 주어졌을 때, M 이상 N 이하의 모든 소수를 구하는 문제입니다.

---

문제 해결 코드

// 에라토스테네스의 체를 이용한 소수 구하기
#include <iostream>
using namespace std;

int arr[1000001];
int main() {
    int a, b;
    cin >> a >> b;

    // 배열 초기화
    for (int i = 2; i <= b; i++) {
        arr[i] = i;
    }

    // 에라토스테네스의 체
    for (int i = 2; i * i <= b; i++) {
        if (arr[i] == 0) continue;
        for (int j = 2 * i; j <= b; j += i) {
            if (arr[j] == 0) continue;
            else arr[j] = 0;
        }
    }

    // 결과 출력
    for (int i = a; i <= b; i++) {
        if (arr[i] != 0) {
            printf("%d\n", arr[i]);
        }
    }
}

---

코드 설명

• 입력: 두 개의 정수 M(a)과 N(b).
• 로직:
  • 1부터 N까지의 자연수를 담은 배열을 준비합니다.
  • 2부터 √N까지 반복하며, 해당 수의 배수를 배열에서 제거합니다.
  • M 이상 N 이하의 배열 값 중 제거되지 않은 값을 출력합니다.
• 출력: M 이상 N 이하의 소수를 한 줄에 하나씩 출력합니다.

시간 복잡도

에라토스테네스의 체를 사용했으므로 시간 복잡도는 O(N log log N)입니다. N은 입력된 최대 범위입니다.

---

결과

이 코드는 에라토스테네스의 체를 활용하여 빠르게 소수를 구합니다. 입력 범위가 클수록 효율적인 방식입니다. 개선할 점이나 더 나은 방법이 있다면 의견을 공유해주세요!