백준 6588번 골드바흐의 추측

< 백준 6588번 골드바흐의 추측 - 마포 코딩박 >

사용한 알고리즘: 에라토스테네스의 체


 문제에서 어떤 짝수 n 이 주어집니다. 두개의 홀수인 소수의 합으로 n 을 만들 수 있는지 묻는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 9~20)
 에라토스테네스의 체로 10^6 까지의 소수를 구합니다. ( n의 최대가 10^6)

(2) (코드 26~38)
 입력된 어떤 수 num에 과정(1) 에서 구해놓은 소수를 빼 보며, 뺀 결과가 홀수인 소수인 경우 이를 출력합니다. ( 단 홀수인 소수는 2보다 큰 수 입니다. )

	#include <iostream>
	#include <vector>
	using namespace std;
	int num;
	bool visited[1000000];
	vector<int> Prime;
	bool flag;
	// 10^6 까지의 모든 소수를 구한다.
	void MakePrime(){
	for (int i = 2; i <= 1000000; ++i){
	if(visited[i]) continue;
	Prime.push_back(i);
	int temp = i;
	while(temp+i<1000000){
	temp += i;
	visited[temp] = true;
	}
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	MakePrime();
	while(1){
	cin >> num;
	if(num == 0) break;
	// 답이 있는지 체크
	flag = false;
	for (int i = 0; i < Prime.size(); ++i){
	// num - 어떤소수 = 소수 인 경우 , 이는 2보다 큰 수여야 한다.
	if(!visited[num-Prime[i]] && num-Prime[i]>2){
	cout << num << " = " << Prime[i] << " + " << num-Prime[i] << '\n';
	flag = true;
	break;
	}
	}
	// 답이 없는경우
	if(!flag)
	cout << "Goldbach's conjecture is wrong." << '\n';
	}
	return 0;
	}

view raw BOJ 6588.cpp hosted with ❤ by GitHub