수학_백준_소수_골드바흐의 추측_6588

지역변수는 메모리가 스택에 잡힌다. 이때 스택은 물리적 메모리 제한이 있으므로, 메모리를 많이 잡아 먹는 것을 지역변수로 설정하면 에러가 뜬다. 따라서 메모리를 많이 쓰는 데이터는 지역변수가 아닌 힙에서 관리하는 전역변수로 설정해야 된다.

물론 전역변수는 처음부터 끝까지 공간을 차지하고, 지역변수는 각 블록이 끝날때마다 공간을 풀어주니 보통 지역변수를 사용하는 것이 더 좋다.

소수는 변하지 않으므로 한 번 구해놓고 이를 활용한다. 또한 이 문제 역시 에라토스테네스의 체를 이용하여 소수를 판별하고 구하자.

#include <iostream>
#define max 1000000
using namespace std;
 
bool  isValue[1000001]; // The value containing the false is a prime number.
int  dp[1000001]; // Set of prime number
//Allocate global variables instead of local variables
 
int main() {
    int index = 0;
    for (int i = 0; i <= max; i++) {
        isValue[i] = false;
    }
 
    for (int i = 2; i <= 1000000; i++) {
        if (isValue[i] == false) {
            dp[index++] = i;
 
            for (long long j = i; (long long)j*i <= max; j++) {
                isValue[i*j] = true;
            }
        }
    }
    //Get a prime number once.
 
    while (true) {
        int n;
        scanf("%d", &n);
        if (n == 0) {
            return 0;
        }
        for (int i = 0; i <=n ; i++) {
            if (isValue[n - dp[i]] == false) {
                printf("%d = %d + %d\n", n, dp[i], n - dp[i]);
                break;
            }
        }
        //Calculate
    }
}