#9020 골드바흐의 추측

# 문제

# 입력 및 출력

# 풀이

에라토스테네스의 체를 활용하여 소수를 구하고 입력받은 n을 반을 나눠서 소수가 맞는지 확인한다

소수가 맞다면 n/2 n/2 로 출력하고, 소수가 아니라면 n/2를 --하면서 값을 소수의 합으로 결과가 나올 때까지 반복함

#include <iostream>
using namespace std;
int prime[1000001];

int main() {
	for (int i = 2; i < 1000001; i++) prime[i] = i;
	for (int i = 2; i < 1000001; i++) {
		for (int j = i + i; j < 1000001; j += i) {
			prime[j] = 0;
		}
	}
	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		int k = n / 2;
		while (1) {
			if (prime[k] && prime[n - k]) {
				cout << k << " " << n - k << "\n";
				break;
			}
			k--;
		}
	}
}

이전에 에라토스테네스의 체를 활용한 문제를 풀면서 그대로 코드를 가져왔더니 

쓸데없이 1,000,000크기로 소수를 확인하고 있었다

해당 문제는 10000크기만 있으면 되므로 다시 줄여주는 과정에서

n을 반으로 나눠서 확인하니까 크기가 5000크기면 되지 않을까해서 줄였다가 틀렸다ㅋㅋ

5000으로 줄이게 되면 k가 소수인지 확인하는 과정에서는 문제가 없지만 n-k가 소수인지 확인하는 과정에서

nullpointerexception 에러가 발생한다

10,000으로 크기를 되돌려주면 제대로 작동한다

 

#include <iostream>
using namespace std;
int prime[10001];
int main() {
	for (int i = 2; i < 10001; i++) prime[i] = i;
	for (int i = 2; i < 10001; i++) {
		for (int j = i + i; j < 10001; j += i) {
			prime[j] = 0;
		}
	}
	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		int k = n / 2;
		while (1) {
			if (prime[k] && prime[n - k]) {
				cout << k << " " << n - k << "\n";
				break;
			}
			k--;
		}
	}
}