[백준/C언어] 9020번 - 골드바흐의 추측

백준 웹사이트 "9020번 - 골드바흐의 추측" 문제풀이입니다.

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

 

---

문제

9020번: 골드바흐의 추측

---

소스 코드

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

void find_prime(int * prime_numbers, int size);

int main(void){
    int prime_numbers[10000];
    for(int index=0; index<10000; index++){
        prime_numbers[index]=index+1;
    }
    find_prime(prime_numbers, 10000); //10000까지의 소수 판별

    int T;
    scanf("%d", &T);
    for(int i=0; i<T; i++){
        int input;
        scanf("%d", &input);

        for(int j=input/2; j>=2; j--){
            int num1 = j;
            int num2 = input - j;

            if(prime_numbers[num1-1]!=0 && prime_numbers[num2-1]!=0){
                printf("%d %d\n", num1, num2);
                break;
            }
        }
    }
}

// 소수들의 배열 반환 함수
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;
                }
            }
        }
    }
}

---

문제 풀이

  이 문제 역시 소수를 이용하는 문제이므로 범위 내 수들의 소수 여부를 미리 구해놓으면 좋겠죠? 10,000까지의 수들에 대해 4948번 문제에서도 이용한 'find_prime' 함수를 적용하면, 배열 'prime_numbers'를 통해 각 수가 소수인지 판별 가능해집니다. 입력된 수를 먼저 반으로 쪼개어 'prime_numbers'로 소수인지 판별하고, 소수가 아니라면 양쪽을 1씩 줄여가며 양쪽 모두 소수가 되는 경우를 구합니다. 10,000 이하의 모든 짝수에 대해 골드바흐 파티션은 존재하므로, 찾지 못할 일은 없습니다!

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

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