[백준] [C++] 9020 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

 

두 가지 방법으로 풀었다. 

 

첫 번째 방법은 숫자 n을 받아서 2로 나눈 후 단순하게 소수 판별을 하고, 

소수가 아니라면 증감을 시키는 방법을 사용하였다. 

 

 

//개별 수에 대해서 소수 판별을 하는 방법

#include <iostream>

bool prime(int n) //소수 판별 함수
{
	for (int i = 2; i * i <= n; ++i)
	{
		if (!(n % i)) return false;
	}
	return true;
}

int main()
{
	int loop;
	std::cin >> loop;

	while (loop--)
	{
		int n;
		std::cin >> n;
		int n1, n2;
		n1 = n2 = n / 2; //입력받은 수를 2로 나눈다

		while (!prime(n1) || !prime(n2)) //두 수 모두 소수가 될 때까지 반복
		{
			--n1; //증감
			++n2;
		}

		std::cout << n1 << ' ' << n2 << '\n';
	}
}

 

 

 

시간을 좀 더 단축시킬 수 있을까 해서 에라토스테네스의 체를 이 문제에도 적용해봤는데, 결과는 여러 번 돌려봐도 거의 비슷하게 나왔다. 

케이스의 수가 많지 않은 경우에는 숫자 하나하나에 대한 소수 판별을 하는 편이 더 효율적일 것 같긴 하다. 

다만 케이스의 수가 많아질수록 체를 사용하는 것이 시간을 더 단축시킬 것 같다.

 

 

//에라토스테네스의 체 사용

#include <iostream>

int main()
{
	bool arr[10001] = { false, }; //문제에서 주어진 범위에 대해 소수 판별
	arr[1] = true;
	
	for (int i = 2; i * i <= 10000; ++i) //i의 배수 지우기
	{
		if (arr[i]) continue;
		for (int j = 2; i * j <= 10000; ++j) arr[i * j] = true;
	}

	int test;
	std::cin >> test;
	
	while (test--)
	{
		int n;
		std::cin >> n;
		int n1, n2;
		n1 = n2 = n / 2;

		while (arr[n1] || arr[n2]) //n1, n2 모두 소수일 때까지 증감
		{
			--n1;
			++n2;
		}

		std::cout << n1 << ' ' << n2 << '\n';
	}
}

 

 

아래가 체를 사용한 코드