[C++] 백준 문제풀이 (Number Theory) 6588번 골드바흐의 추측

코딩준우 2023. 7. 5. 18:17

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net

#include <bits/stdc++.h>
// [C++] 백준 문제풀이 (Number Theory)
int n;
bool primes[1000001];



int main(int argc, char *argv[])
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	for (int i = 2; i * i < 1000001; ++i){
		if (primes[i]) continue;
		for (int j = i * i; j < 1000001; j += i){
			primes[j] = true;
		}
	}
	
	while(1)
	{
		std::cin >> n;
		if (n == 0) break;
		int left = 3;
		int right = n - 3;

		while(left <= right)
		{
			if(!primes[left] && !primes[right])
				if(left + right == n)
					break;
			left += 2;
			right -= 2;
		}

		if(left > right)  
			std::cout<<"Goldbach's conjecture is wrong.";
		else 
			std::cout << n << " = " << left << " + " << right << '\n';
	}
	return 0;
}