[C]백준 Q.6588 골드바흐의 추측

https://www.acmicpc.net/problem/6588

 

오랜만에 코오오오딩...

12월 중순에 짧은거 올린후로는 손을 안댔다가 어느샌가 잊고있었다.

2026년이 밝았고 만약 이글을 읽는분이 있다면 새해복 많이 받을것이다.

 

/** 잡썰

그렇게 신년들어 첫 코딩이 이런 수학문제

뭔가 아쉽다만 어쩔 수 없지 다른건 너무 오래걸린다

요새.. 12월엔 연운이라는 게임을 하고있고 게임내 미니게임인 중국장기 문제풀이를 도와줄 프로젝트를 만들고있었는데 

이것좀 그만 미루고 완성시켜서 글을써야할텐데... 아무튼 문제를풀자

**/

 

 

이번문제는 4보다큰 모든 짝수는 두개의 홀수인 소수의 합 형태로 나타낼 수 있다. 라는걸 짧게 증명해보는 문제다

필요한건

이 수가 홀수인가? 라는걸 체크해볼 코드이다

사실 이건 이 문제가 포함된 문제집인 "코딩 테스트 준비 - 기초" 의 이 골든바흐의 추측 이전 코드로 이미 만들었다

그래서  1929번 문제코드를 그냥 그대로 뜯어와서 출력해주는 조건문의 역할을 저장해주는 역할로 바꿔줬다

그래서 소수값을 저장해줄 배열을 전역으로 선언해줬었고, 소수인지 판별은 따로 하지않고 미리 계산해둔값으로 판별( 사실 코드로 할까하다가 미리 만든 p배열로 체크하자! 라고하다가.... 다시 계획을 바꿔 따로 저장해줬다.)하는 check배열을 전역으로 만들어줬다

check배열은 인덱스로 들어온값이 가르키는 값이 0인지 1인지를 반환해줄거고 이를 통해 이값이 소수인지를 판별하게 만들어서 0으로 초기화를 해줬다~

 

뭐 그렇게 들어오는 타겟값에서 작은 소수를 빼줘서 남은 수가 소수인가?를 판별해서 나오면 바로 출력해주는거로 문제끝

#include <stdlib.h>
#include <stdio.h>

/**
 q6588 골드바흐의 추측
 
 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
 입력의 마지막 줄에는 0이 하나 주어진다.
 */
#define MAX 1000000

long long p[MAX];
long long check[MAX] = {0};
long LAST = 0;

void setupPrime(int min, int max) {
    if (min < 2) min = 2;

    long pIndex = 0;
    
    for (int i = min; i <= max; i++) {
        int isPrime = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = 0;
                break;
            }
        }
        
//        if (isPrime) printf("%d\n", i);
        if (isPrime) {
            p[pIndex] = i;
            check[i] = 1;
            LAST = pIndex;
            pIndex ++;
        }
    }
}


/// n = a + b 형태로 출력
void findCombin(long n) {
    long pIndex = 0;
    
    while (pIndex < LAST) {
        long a = p[pIndex];
        long b = n - p[pIndex];
        if (check[b] == 1) {
            // 8 = 3 + 5
            printf("%lu = %lu + %lu\n", n, a, b);
            return;
        }
        pIndex ++;
    }
    
    printf("Goldbach's conjecture is wrong.");
    return;
}

int main(int argc, const char * argv[]) {
    setupPrime(3, MAX);
    
    long target = 0;
    while (scanf("%lu", &target) != EOF && target != 0) {
        findCombin(target);
    }
    
    return EXIT_SUCCESS;
}

 

 

아래는 깃 레포지토리 링크!

아직 깃허브에 쓰고있긴한데.... 사실 12월에 codeberg라는 깃사이트를 가입했다

이곳으로 옴겨볼까 하고있는중이라 우선 키보드 프로젝트만 복사해놨긴했는데 그냥 막 넘기지않고 레포지토리를 좀 통합해서 옴겨볼까~도 생각중이라 아직 깃허브에 업로드중이다

 

 

https://github.com/wiwi-git/c-baekjoon/tree/main/q6588

c-baekjoon/q6588 at main · wiwi-git/c-baekjoon