백준 9020번 골드바흐의 추측

9020번: 골드바흐의 추측 (acmicpc.net)

9020번: 골드바흐의 추측

 

 

문제 요약: 골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션을 존재한다. 2보다 큰 짝수 n이 주어졌을 때, 두 소수의 차이가 가장 작은 n의 골드바흐 파티션을 출력하라. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다. 

 

 

 

문제 풀이: 나는 이 문제를 두 수의 차이가 가장 작은 값으로 출력하라는 것에서 먼저 n을 2로 나눠서 두 개의 변수에 저장하였다. 그 후 만약 값이 소수가 아닐 경우 A 변수는 -1, B변수는 +1을 해줘서 애초에 가장 차이가 가장 작은 소수 값을 구하도록 구현했다. 예를 들어, 1000의 골드바흐 파티션을 구한다고 가정하면 각각의 변수에 500을 저장하고, 소수가 아닐 경우 한쪽은 -1씩, 다른 한쪽은 +1을 해줘서 두 변수가 모두 소수라면 그 값을 출력한다는 것이다.  

 

 

 

http://colorscripter.com/s/80U8Jwc

공유된 코드 - Color Scripter