[백준/C언어] 4948번 - 베르트랑 공준

백준 웹사이트 "4948번 - 베르트랑 공준" 문제풀이입니다.

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

 

---

문제

4948번: 베르트랑 공준

---

소스 코드

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

void find_prime(int * prime_numbers, int size);

int main(void){
    // 시간 초과 -> 최댓값 123456*2에 대해 prime_numbers 한 번만 실행
    // 에라토스테네스의 체 이용
    int max = 123456*2;
    int prime_numbers[max];
    for(int num=0; num<max; num++){
        prime_numbers[num] = num+1;
    }
    find_prime(prime_numbers, max);

    while(1){
        int n;
        scanf("%d", &n);
        if(n==0)
            break;
    
        int count = 0;
        for(int i=n; i<=2*n-1; i++){ //숫자 n은 prime_numbers[n-1]에 위치
            if(prime_numbers[i]!=0){
                //printf("prime: %d\n", prime_numbers[i]);
                count++;
            }
        }
        printf("%d\n", count);
    }
}

// 소수들의 배열 반환 함수
void find_prime(int * prime_numbers, int size){
    int max_factor = (int) sqrt((double) size);
    //printf("max factor: %d\n", max_factor);
    prime_numbers[0]=0; //prime_numbers[0]은 1로, 소수가 아니므로
    for(int i=2; i<=max_factor; i++){
        for(int j=0; j<size; j++){
            if(prime_numbers[j]!=0){
                if(prime_numbers[j]==i){
                    //소수 (i가 소수가 아닐 경우, 이미 0으로 바뀜)
                    continue;
                }
                if(prime_numbers[j]%i==0){
                    //printf("Not prime: %d\n", prime_numbers[j]);
                    prime_numbers[j]=0;
                }
            }
        }
    }
}

---

문제 풀이

  이전 1929번 문제에 이어 시간 초과에 걸리지 않기 위해 '에라토스테네스의 체'를 활용하는 문제입니다. 더 나아가, 이 문제에서는 에라토스테네스의 체를 딱 한 번만 이용해야 합니다. 사용자가 "0"을 입력할 때까지 계속해서 새로운 입력을 받는데, 입력을 받을 때마다 엘토스테네스의 체를 이용하면 이 역시 제한 시간이 초과됩니다.

  그렇다면 크기가 얼마나 될지 모르는 입력들을 모두 만족시키기 위해서 체를 어떻게 활용해야 할까요? 최대 범위 내 모든 수들에 대해 에라토스테네스의 체를 사용하여 어느 숫자들이 소수인지 미리 모두 구해놓으면 됩니다. 이들을 배열에 기록해둔 후, 입력이 들어올 때마다 배열을 참고하여 해당 범위 내 소수의 개수를 출력하는 것입니다. 에라토스테네스의 체를 직접 시행하는 것과 달리, 단순히 배열을 참고하는 것은 매우 짧은 시간이 걸리기에 시간 제한이 걸릴 위험이 없습니다.

  문제에 제시된 n의 최댓값은 123,456이고, n이 입력되면 최대 2n까지의 수들을 검사해봐야하니, 123,456×2 이하의 수들에 대해 체를 활용하면 됩니다. 소수들의 배열을 반환하는 함수는 'find_prime' 함수로, 1929번에 작성한 코드와 비슷합니다. 새롭게 선언 및 초기화한 배열 'prime_numbers'를 find_prime 함수에 넣으면 소수만 남은 배열이 반환됩니다. 이후, while문을 통해 입력을 받을 때마다 정리된 prime_numbers 배열을 참고하면 범위 내 소수의 개수를 빠르게 구할 수 있습니다.  

  에라토스테네스의 체에 대한 추가 설명은, 백준 웹사이트 "1929번 - 소수 구하기" 문제풀이 링크를 참고해주세요!

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