[백준/C언어] 1929번 - 소수 구하기

백준 웹사이트 "1929번 - 소수 구하기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

 

1929번: 소수 구하기

---

소스 코드

#include <stdio.h>
#include <math.h>

int main(void){
    int M, N;
    scanf("%d %d", &M, &N);

    //시간 초과 -> 에라토스테네스의 체 이용
    int prime_numbers[N-M+1];
    for(int num=0; num<N-M+1; num++){
        prime_numbers[num] = M+num;
    }

    int max_factor = (int) sqrt((double) N);
    for(int i=2; i<=max_factor; i++){
        for(int j=0; j<N-M+1; j++){
            if(prime_numbers[j]!=0){
                if(prime_numbers[j]==i){
                    // 소수 (소수가 아닐 경우, 이미 0으로 바뀜)
                    continue;
                }
                if(prime_numbers[j]%i==0){
                    //printf("Not prime: %d\n", prime_numbers[j]);
                    prime_numbers[j]=0;
                }
            }
        }
    }
    if(prime_numbers[0]==1){
        prime_numbers[0]=0;
    }

    for(int k=0; k<N-M+1; k++){
        if(prime_numbers[k]!=0){
            printf("%d\n", prime_numbers[k]);
        }
    }
}

---

문제 풀이

  굉장히 쉬운 문제인줄 알았으나, '시간 초과'에 걸려버리고 다시 푼 문제입니다. 지금까지 해왔던 방식대로 소수인가를 검증하면 시간 초과에 걸리게 됩니다. N의 최댓값은 1,000,000이기에, 만약 M=1, N=1,000,000이라면 그 사이에 있는 모든 수들을 하나씩 검증해야하고, 그렇게 하는데 많은 시간이 걸립니다. 시간을 줄이기 위해, '에라토스테네스의 체'라는 방법을 이용합니다. 이 방법을 잘 모르는 분들은 아래 GIF를 참고해주세요. 2를 소수로 표시한 후 모든 2의 배수를 지우고, 3을 소수로 표시한 후 모든 3의 배수를 지우고, ... 반복하여 특정 구간의 모든 소수를 구하는 방법입니다.

에라토스테네스의 체 (출처: 위키피디아 "에라토스테네스의 체")

  보통 에라토스테네스의 체는 2부터 시작을 하지만, 이 문제에서는 시간을 더욱 줄이기 위해 M부터 시작합니다. 그렇다고 해서 M을 소수로 표시하고 지우는 것은 물론 아니고, 2부터 시작하여 오름차순으로 소수들의 배수를 지워줍니다. 이 과정을 최대 수인 N의 제곱근까지 반복하며, 제곱근이 정수가 아닐 경우에는 그 제곱근의 정수 부분까지 반복합니다.

  이러한 에라토스테네스의 체를 구현한 것이 위의 소스 코드입니다. 소수들의 배열 'prime_numbers'를 필요한 구간만큼 선언한 후, 필요한 구간의 숫자들로 초기화합니다. 그 후, 에라토스테네스의 체로 소수들을 하나씩 걸러주며, 만약 소수라면 그대로 두고 소수가 아니라면 배열에서 그 수를 0으로 바꿉니다. 0으로 바꾸는 것이 '지우는' 과정이므로, 이후의 검사들에서는 배제해도 괜찮습니다. 이러한 과정을 통해 얻게 되는 최종적인 'prime_numbers'에는 소수들만 남게 되고, 소수가 아닌 수들은 모두 0으로 치환됩니다.