백준 6588번 - 골드바흐의 추측

교수님이 프로젝트 과제를 내주셨는데 백준 문제 6588번과 비슷한 것 같다.

 

문제 링크

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

6588번: 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

교수님이 내주신 문제

에라토스테네스의 체를 이용해 소수  판별 배열을 완성시킨다. 이후 주어진 짝수를 차이가 최소가 되는 두 소수 i, j로 쪼개서 출력한다.(i<=j)

 

에라토스테네스의 체 ???

간단하게 말하면, 어떤 소수를 구하면, 그 소수의 배수들은 다 소수가 아니니까 미리 체크해둬서, (체를 친다!)

체크가 안 된 수들만을 구하면 소수들을 쉽게 알게 된다. 

 

100까지의 모든 소수를 구한다고 가정해보자.

 

2부터 100까지 배열에 모두 넣은 후, 소수가 아닌 것들을 모두 체크해버리는 것이다.

 

2를 제외한 모든 2의 배수를 체크한다.

3을 제외한 모든 3의 배수를 체크한다.

4는 아까 2의 배수에서 이미 체크되었다.

5를 제외한 모든 5의 배수를 체크한다.

 

이렇게 100까지 진행하고, 이 중에서 체크가 안된 수들이 소수이다.

 

<풀이순서>

1. 에라토스테네스의 체를 이용하여 소수인지 아닌지 체크해주고,

2. testcase 만큼 num을 입력받고,  처음부터 MAX까지 j와 num-j가 모두 소수인 것을 찾는다.

3. 찾으면 바로 break 걸고 출력하고 끝낸다.

 

처음에는

"N/2를 중심으로, N/2 - i과 N/2 + i 모두가 소수가 되도록 하는 i의 값을 찾고,

N/2 - i 와 N/2 + i의 값을 출력하면 쉽게 해결할 수 있다" 고 해서, 중간값부터 접근하려고 하였으나,

문제에서 이 상황을 만족하는 조합들이 많으면 a가 가장 작은 것을 출력하라고 하였기에

앞부분부터 하는 것이 낫겠다는 생각이 들었다.

-> 백준 9020번 문제에서는 두 소수의 합이 여러가지가 있다면 두 수의 차가 제일 적은 수를 구하는 것이 문제였기 때문에,

중간값부터 접근해야 한다. N의 절반인 수를 기준으로 하나의 수는 1씩 감소하고 다른 하나는 1씩 증가해야한다!

 

핵심 아이디어

소수는 에라토스테네스의 체를 이용해서 n의 범위만큼 미리 구해서 배열에 저장한다.

n이 두 소수 p와 q로 이루어져 있다고 했을 때,

p + q = n

n - p = q

이므로 n에서 소수를 뺀 값이 소수이면 답을 바로 출력한다.

 

참고로 c++에서

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

를 써주면 입출력 속도를 높일 수 있다고 한다. 

대신에 printf, scanf 등은 사용하면 안 된다.

 

하지만 나는 printf, scanf가 더 빠른 것 같아서 cin, cout을 사용하지 않았다. 😀

 

 

 

나의 풀이 (백준 6588번)

#include <iostream>

using namespace std;

const int MAX = 1000000;

bool check[MAX+1];

int main() {
    int T, num;

    //먼저 에라토스테네스의 체를 이용해 소수를 구해준다. 소수이면 false, 소수가 아니면 true
    for(int i = 2; i * i <= MAX; i++) {
     //이미 소수가 아닌걸로 체크되어 있는 경우
      if(check[i] == true) continue;

      //현재 i의 배수들은 소수가 아니므로 체크해준다.
      for(int j = i * i; j <= MAX; j+=i) { 
        check[j] = true;
      }
    }

    while(1) {
        scanf("%d", &num); //숫자를 입력받는다.
        if (num == 0) {
            break;
        }
        for (int j = 2; j < MAX; j++) {
            if (check[j] == false) {
              if (check[num-j] == false) {
                //printf("Case #%d:\n", i+1);
                printf("%d = %d + %d\n", num, j, num-j);
                break;
              }
            }
         }
    }

    return 0;
}