[C++/백준 6588번] 골드바흐의 추측

 

 

 

에라토스테네스의 체를 사용하여 소수를 판별 한 뒤, 출력한다.

에라토스테네스의 체란 i 의 배수들을 제거해 나가며 소수를 판별해 나가는 방법인데, 시간 복잡도가 O(N log(logN)) 이다.

iostream과 stdio.h 가 동기화 되어 있을 때는 cout 을 통한 출력 속도가 느림에 주의하자.

 

 

#include <iostream>
#include <cmath>
using namespace std;

int check[1000001] = { false };

void Primearr(int input)
{

	for (int i = 2; i < 1000; i++)
	{
		if (check[i] == false)
		{
			for (int j = i * i; j <= input; j += i)
			{
				check[j] = true;
			}
		}

	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int input = -1;

	Primearr(1000001);
	while (1)
	{

		cin >> input;
		if (input == 0) break;

		bool can = false;
		
		for (int i = 3; i <= input; i+=2)
		{
			if ( !check[i] && ! check[input-i])
			{
				cout << input << " = " << i << " + " << input - i << '\n';
				can = true;
				break;
			}
		}
		
		if (!can) cout << "Goldbach`s conjecture is wrong.";

	}




	return 0;
}