https://www.acmicpc.net/problem/6588
에라토스테네스의 체를 사용하여 소수를 모두 구해두었다.
그 다음, 주어진 숫자를 홀수 소수의 합으로 구할 수 있는지 살펴보았다.
불가능한 경우를 나타내기 위해 투포인터의 개념을 적용하였다.
#include <iostream>
#include <math.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int primeNum[1000001] = { 0, };
primeNum[1] = 1;
for (int i = 2; i <= sqrt(1000000); i++) {
if (primeNum[i] == 1) continue;
for (int j = 2 * i; j <= 1000000; j += i) {
primeNum[j] = 1;
}
}
int n;
while (1) {
cin >> n;
if (n == 0) break;
for (int left = 3; left <= n / 2 + 1; left += 2) {
int right = n - left;
if (left > right) {
cout << "Goldbach's conjecture is wrong.\n";
break;
}
if (primeNum[left]) continue;
if (primeNum[right] == 0) {
cout << n << " = " << left << " + " << right << '\n';
break;
}
}
}
return 0;
}
문제를 풀며 stack overflow를 마주하였다. 범위가 큰 primeNum 배열을 main 함수 내부에서 정의하여 발생한 것이였다.
그 원인은 배열이 할당되는 위치에 있었다.
main 함수 내에서 선언된 배열은 스택 영역에 생성된다. 스택영역은 프로그램이 사용하는 임시 메모리로 할량할 수 있는 정도가 적다.
해당 배열을 전역 변수로 설정하여 문제를 해결할 수 있었다.
전역변수로 변수를 선언하면 이는 함수가 호출되기 전에 메모리의 데이터 영역에 할당된다.