9020번 - 골드바흐의 추측

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

9020번: 골드바흐의 추측

무작정 1부터 늘려가며 비교를 했는데 시간초과 오류가 떴다.

그래서 다시 생각해보니 중간값에서 멀어지는 것이 두 소수의 차이가 가장 작은 값을 찾는 더 빠른 방법일거라 생각했다. 

 

소수를 구하는 방법은 

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

1929번: 소수 구하기

를 풀어보자!

#include <iostream>
#include <math.h>
using namespace std;
bool *primenumber;
//에라토스테네스의 체를 활용한 소수 구하기
void prime(int n)
{
  primenumber = new bool[n+1];
  fill_n(primenumber, n+1, 1);
  primenumber[0] = false; //0은 소수가 아님
  primenumber[1] = false; //1은 소수가 아님
  for(int i=2; i<=sqrt(n); i++)
  {
    if(primenumber[i] == true)
      for(int j=2*i; j<=n; j+=i)
        primenumber[j] = false;
  }
}
//골드바흐의 추측
void goldbach(int n)
{
  //짝수의 중간값에서 1씩 멀어지며 탐색하기
  for(int j=n/2; j>0; j--)
    //j + (n-j) == n
    if(primenumber[j] && primenumber[n-j])
    {
      //만족하게 된다면 그 값이 가장 차가 적은 소수의 합
      cout << j << " " <<n-j << '\n';
      return ;
    }
}
int main() {
  int T;
  cin >> T;
  int N; //4<=N<=10,000
  for(int i=0; i<T; i++)
  {
    cin >> N;
    prime(N); //소수판별
    goldbach(N); //골드바흐의 추측
  }
  return 0;
}