백준 9020_골드바흐의 추측.cpp

<소스코드>

#include <iostream>
#include <cmath>
using namespace std;
int* Erathosteness(int a, int b){
    int* arr;
    arr = new int[b+1];
    for(int i = 2; i <= b; i++){
        arr[i] = i;
    }
    for(int i = 2; i <= sqrt(b); i++){
        if(arr[i] == 0){
            continue;
        }
        for(int j = i*i; j <= b; j += i){
            arr[j] = 0;
        }
    }
    return arr;
}

bool check(int n){
    for(int j = 2; j <= sqrt(n); j++){
        if(n%j == 0){
            return false;
        }
    }
    return true;
}

int main(){
    int NumTestCases;
    cin >> NumTestCases;
    for(int i = 0; i < NumTestCases; i++){
    int num;
    cin >> num;
    int *arr = Erathosteness(1,num/2);
    for(int i = num/2; i >= 2; i--){
        if(arr[i] != 0){
            if(check(num-arr[i])){
                cout << arr[i] << " " << num-arr[i] << endl;
                break;
                }
            }
        }
        delete arr;
    }
    return 0;
}

1. 변수&함수
   int Erathosteness(int a, int b) : 범위 내에 소수를 찾아주는 함수
   bool check(int n) : 소수판별함수
   int NumTestCases : 테스트케이스 개수
   int num : 입력받은 정수
   int arr : 소수 배열(Erathosteness의 리턴값)

2. 알고리즘
   1) 에라토스테네스의 체를 활용한 함수로 2부터 2/n까지의 소수배열 구하기
   why? 절반만 구하면 나머지 값은 num에서 빼주면 저절로 나온다.
   2) 배열을 끝에서부터 돌면서(why? 끝에서부터 돌아야 차이가 최소가 된다.) 만약 소수라면
   check 함수를 통해서 num-소수도 소수인지 확인한다.
   3) 맞다면 출력하고 배열을 delete해준다.

3. 배운점

• new, delete를 사용한 동적 메모리 할당
  1) 단일 변수를 동적 할당 : new int;
  2) 할당된 메모리에 나중에 접근하도록 하려면
  
  3) 동적배열 할당
  int* 배열이름 = new 타입[배열크기+1];
  why (배열크기 +1)? 문자열 길이 + 1 바이트 만큼 할당해야 된다!
  delete 배열이름

4. 아쉬운점&느낀점
   앞으로는 malloc보단 new, delete를 많이 활용해야겠다. 계속 런타임에러가 나서 힘들었는데 디버깅을 열심히 해서 해결했다는게 기분이 좋았다. 이 문제를 끝으로 소수 문제가 끝났는데 정말 많이 배운거 같다!