[백준] 1929번: 소수 구하기 - C++ (+ 에라토스테네스의 체)

문제

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

 

입력

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

 

출력

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

---

앞서 1978번 소수 찾기에서 풀었던 특정 수에 대한 소수 판정을 확장하여 특정 범위 내의 소수를 모두 구하는 알고리즘인 에라토스테네스의 체를 이용하여 풀 수 있는 문제이다.

말이 어렵지만, 원리가 간단하다. 2 이상의 구하고자 하는 범위 내에 존재하는 자연수를 모두 나열한 뒤, 2의 배수부터 3의 배수, 4의 배수, ... 등 차례로 그 수의 배수들을 지워나간다.

 

예를 들어, 다음과 같이 2부터 50까지의 범위 내에 존재하는 소수를 에라토스테네스의 체를 이용해 구해보도록 한다.

1단계 : 2를 제외한 2의 배수를 모두 제외한다.

2단계 : 3을 제외한 3의 배수를 모두 제외한다.

3단계 : 4의 배수는 앞서 1단계에서 모두 제외되었으므로, 5를 제외한 5의 배수를 모두 제외한다.

4단계 : 앞선 단계들과 마찬가지로 아직 지워지지 않은 7의 배수, 11의 배수 .. 등을 지워나가게 되면 위와 같이 최종적인 소수들이 남게 된다.

따라서 2와 50 사이에 존재하는 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47이다.

 

코드는 다음과 같다. 2부터 N까지의 배열에서 0으로 기록된 값의 인덱스가 곧 소수가 된다. 에라토스테네스의 체의 시간복잡도는 O(N log(log N))으로 매우 빠르게 작동한다.

for(int i = 2; i * i <= N; i++) {
    if(arr[i] == 0) continue;	// 이미 수가 지워진 경우 넘어감
    for(int j = 2 * i; j <= N; j += i) {
    	if(arr[j] == 0)  continue;	// 소수가 아닌 경우 넘어감
        else arr[j] = 0;	// 소수를 지움
    }
}

 

+ 기본적으로 에라토스테네스의 체를 이용하여 문제를 풀었는데, 시간 제한이 넉넉한게 혹시나 싶어 앞서 구한 소수 판정 방식으로 풀어봤는데 통과가 되긴 했다.

 

코드

#include <cstdio>
#include <vector>

using namespace std;

int main(void) {
    int m, n;
    scanf("%d %d", &m, &n);
    
    vector<int> arr(n + 1, 0);

    for(int i = 2; i <= n; i++) {
        arr[i] = i;
    }

    for(int i = 2; i * i <= n; i++) {
        if(arr[i] == 0) continue;
        for(int j = 2 * i; j <= n; j += i) {
            if(arr[j] == 0)  continue;
            else arr[j] = 0;
        }
    }

    for(int i = m; i <= n; i++) {
        if(arr[i] != 0) printf("%d\n", arr[i]);
    }
    return 0;
}