[백준] 6588번 골드바흐의 추측 (C++)

문제

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

6588번: 골드바흐의 추측

코드

내 풀이

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  vector<int> primeN;
  for(int i=2; i<1000; i++){
    bool flag = true;
    for(int j=2; j<=sqrt(i); j++){
      if(i%j==0){
        flag = false;
        break;
      }
    }
    if(flag) primeN.push_back(i);
  }

  while(true){
    int n;
    cin >> n;
    if(n==0) break;
    for(int i=0; i<primeN.size(); i++){
      bool flag = true;
      for(int j=2; j<=sqrt(n-primeN[i]); j++){
        if((n-primeN[i])%j==0){
          flag = false;
          break;
        }
      }
      if(flag){
        cout << n << " = " << primeN[i] << " + " << n-primeN[i] << '\n';
        break;
      }
    }
  }
  return 0;
}

 

다른 사람 풀이

#include <iostream>
#include <vector>

using namespace std;

bool check[1000001];
vector<int> primeN;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  for (int i = 0; i < 1000001; i++) check[i] = true;
  for(int i=2; i*i <= 1000000; i++){
    if(check[i]){
      for(int j=i*i; j<=1000000; j+=i){
        check[j] = false;
      }
    }
  }

  for(int i=2; i<=1000000; i++){
    if(check[i]) primeN.push_back(i);
  }

  while(true){
    int n;
    cin >> n;
    if(n==0) break;
    for(int i=0; primeN[i]<n; i++){
      int n2 = n-primeN[i];
      if(check[n2]){
        cout << n << " = " << primeN[i] << " + " << n-primeN[i] << '\n';
        break;
      }
    }
  }

  return 0;
}

정리

우선 소수들을 vector에 저장해 놓은 다음에 그 소수들을 입력받은 수에 하나씩 빼가면서 두 홀수 소수의 합을 구하려고 계획을 세웠다. 그러기 위해서는 vector에 저장해 놓을 소수가 최대 몇인지 알아야 하는데 알 길이 없었다. 그래서 처음에는 입력받는 수의 최대인 100000까지의 소수를 구하려고 했다. 그러나 100000까지의 소수를 구하는 과정은 시간이 엄청 오래 걸렸다. 보완책으로 그냥 될되로돼라는 식으로 1000까지의 소수를 구하였더니 문제가 풀렸다. 그러나 이렇게 푸는 것은 좋은 풀이가 아니다. 정확한 이유를 모르고 푼 문제이기 때문이다.

그래서 다른 사람의 코드를 참고해 보았다. 에라토스테네스의 체를 이용하여 문제를 풀었다. check라는 bool array를 따로 만들어서 발견한 소수의 배수들은 소수가 아니기 때문에 false 처리를 해주었다. 이 방법은 1000000까지의 소수를 구해도 소수를 구하고 소수의 배수들을 제거하면서 진행하기 때문에 시간이 많이 걸리지 않았다.

for (int i = 2; i * i <= n; i++)
	{
		if (PrimeArray[i])
			for (int j = i * i; j <= n; j += i)
			    PrimeArray[j] = false;
	}

소수 관련 문제가 나오면 이 방법을 사용해야겠다.

참조

https://minocode.tistory.com/18

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4