[BOJ - 17103] 골드바흐 파티션

💡문제 한마디

에라토스테네스의 체를 활용한 소수 판정문제인데, 여기서 메모리를 많이써서 시간을 줄일지, 시간을 사용해서 메모리를 덜 쓸지 고민했던 문제

문제 링크

골드바흐 파티션

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(void){

  int T,count=0;
  int max=0;

  cin >> T;
  vector<int> N(T);

  for(int i=0;i<T;i++){
    cin >> N[i];
    if(max<N[i]){
      max = N[i];
    }
  }
  vector<bool> B(max+1,true);
  vector<int> C(max+1);

  B[0]=false;
  B[1]=false;
  for(int i=2;i<max+1;i++){
    if(B[i]==true){
      C[count++] = i;
      for(int j=i*2;j<max+1;j+=i){
        B[j] = false;
      }
    }
  }

  for(int i=0;i<T;i++){
    float T_count =0;
    for(int j=0;j<count;j++){
      if(C[j]>=N[i]){
        break;
      }
      if(B[N[i]-C[j]]){
        T_count++;
      }
    }
    cout << (int)(ceil(T_count/2)) << '\n';
  }
}

풀이

  vector<bool> B(max+1,true);
  vector<int> C(max+1);
  B[0]=false;
  B[1]=false;
  
    for(int i=2;i<max+1;i++){
      if(B[i]==true){
        C[count++] = i;
        for(int j=i*2;j<max+1;j+=i){
          B[j] = false;
        }
      }
    }

에라토스테네스의 체를 구현한 코드

• 0,1은 소수가 아니니 false로 지정
• 2부터 시작해서 소수가 나오면 그 소수의 배수들은 모두 false로 지정 + 소수는 소수만 있는 저장공간에 저장( 이것때문에 메모리를 많이 사용했음.)

  for(int i=0;i<T;i++){
    float T_count =0;
    for(int j=0;j<count;j++){
      if(C[j]>=N[i]){
        break;
      }
      if(B[N[i]-C[j]]){
        T_count++;
      }
    }
    cout << (int)(ceil(T_count/2)) << '\n';
  }

골드바흐의 추측을 구현한 코드

• 판정하려는 소수를 A, 백터 C에 있는 소수를 P라고 했을 때, A-P가 소수면 골드바흐의 추측에 해당하는 케이스가 됨.
• 따라서 A == N[i], P == C[j] 일 때 B[N[i]-C[j]] == true면 골드바흐 추측에 해당하는 값이므로 count를 +1해주면 됨.
• 그리고 순서가 뒤바뀐 경우는 중복 처리 해주어야 하므로 2로 나눈 뒤 올림해주면 끝