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

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

9020번: 골드바흐의 추측

코드

#include <iostream>
using namespace std;

bool Prime_number[10001];

void find_Prime()
{
	Prime_number[1] = true;
	for(int i=2; i<10001; i++)
	{
		if(!Prime_number[i])
		{
			for(int j = i * 2; j < 10001; j += i)
			{
				Prime_number[j] = true;
			}
		}
	}
}

int main() {
	find_Prime();
	int t, n, low = 0, high = 0;
	cin >> t;
	
	for(int i=0; i<t; i++)
	{
		cin >> n;
		for(int j=2; j < (n/2)+1; j++)
		{
			if(!Prime_number[j] && !Prime_number[n - j])
			{
				low = j;
				high = n - j;
			}
		}
		cout << low << " "  << high << endl;
	}
	return 0;
}

 

설명

토라토스테네스의 체를 사용하면 풀 수 있는 문제이다...

이정도면 백준 단계별 문제풀이에서 수학2는 그냥 소수찾기로 바꿔야하는게 아닐까?

모든 수는 두 소수의 합으로 나타낼수 있다고 하니...

예를들어 주어진 수가 20이라고 해 보자.

그러면 우리는 10까지의 소수만 찾으면 된다.

소수 2 3 5 7

2일때는 18과 더해져야 20이 되는데 18이 소수가 아니므로  X

3일때는 17과 더해져야 20이 되는데 17이 소수이므로 O

5일때는 15와 더해져야 20이 되는데 15가 소수가 아니므로 X

7일때는 13과 더해져야 20이 되는데 13이 소수이므로 O

두 수 간의 차이가 가장 작으려면 그냥 가장 마지막에 O였던 수를 호출하면 되므로

7 13을 호출하면 된다.

이런 식으로 풀면 되는 문제.