백준 6588 c++ "골드바흐의 추측" -PlusUltraCode-

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

[필자 사고]

에라토스테네스의 채 알고리즘을 알고 있으면 해당 문제를 쉽게 해결할 수 있다.

초기에 해당 소수들을 판정한 뒤

주어진 숫자들을 3, 5 ,7 등 소수 홀수부터 점검하여 diff 가 소수라고 한다면 문제 해결이다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input_Init()

• 소수 판별을 위해 isPrime 벡터를 크기 MAX+1로 true로 초기화한 후, 에라토스테네스의 체 알고리즘을 사용해 소수가 아닌 수를 false로 설정함.
• 0과 1은 소수가 아니므로 false로 설정함.
• 2부터 sqrt(MAX)까지 순회하면서, 해당 수가 소수이면 그 배수들을 모두 소수가 아닌 것으로 표시함.

---

Print(int num, int leftSosu, int rightSosu)

• num = leftSosu + rightSosu 형식으로 결과를 출력함.
• 골드바흐의 추측에서 제시한 두 소수의 합을 출력하는 역할임.

---

Game_Start(int num)

• num을 두 개의 소수의 합으로 나타낼 수 있는지를 검증하는 함수.
• 3부터 MAX까지 홀수 중에서 소수만 검사하며 반복함.
• 현재 소수 i를 기준으로 num - i가 소수인지 확인.
• 조건을 만족하면 두 소수의 합으로 num을 표현하고 종료.
• 만약 해당 조건을 만족하는 두 소수를 못 찾으면 "Goldbach's conjecture is wrong."를 출력하고 종료함.

---

main()

• 빠른 입출력을 위해 ios::sync_with_stdio(false)와 cin.tie(0), cout.tie(0) 설정.
• Input_Init()을 호출하여 소수 판별 배열을 초기화.
• 무한 루프를 통해 사용자로부터 수를 계속 입력받음.
• 입력이 0이면 루프를 종료.
• 입력받은 수에 대해 Game_Start() 함수를 호출하여 골드바흐의 추측을 검증함.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 1000000
using namespace std;
vector<bool> isPrime;

void Input_Init() {
	isPrime.resize(MAX + 1,true);
	isPrime[0] = false;
	isPrime[1] = false;
	
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (isPrime[i] == false) continue;
		for (int k = i * i; k <= MAX; k += i) {
			isPrime[k] = false;
		}
	}
}

void Print(int num, int leftSosu, int rightSosu) {
	cout << num << " = " << leftSosu << " + " << rightSosu << '\n';
}

void Game_Start(int num) {
	for (int i = 3; i <= MAX; i+=2) {
		if (isPrime[i] == false)continue;
		int diff = num - i;
		if (diff <= 2) {
			cout << "Goldbach's conjecture is wrong.";
			break;
		}
		if (isPrime[diff]) {
			Print(num, i, diff);
			break;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Input_Init();
	while (1) {
		int num;
		cin >> num;
		if (num == 0)break;
		Game_Start(num);
	}
}