백준 6588 골드바흐의 추축 (c++) : 피너클

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

6588번: 골드바흐의 추측

 

 

범위 안의 소수를 어떻게 찾을것인지와 두 홀수 소수의 합으로 n을 어떻게 나타낼것인지가 관건이다.

 

bool visited[1000001];
vector<int> v;

bool visited에는 소수인지 아닌지 여부가 들어갈 것이다.

vector<int> v에는 소수가 들어갈것이다.

for (int i = 3; i <= 1000000; i += 2) {
	if (!visited[i]) {
		v.push_back(i);
		for (int j = i + i; j <= 1000000; j += i) {
			visited[j] = true;
		}
	}
}

에라토스테네스의 채다. 처음 visited는 모두 false로 선언된다.

만약 visited[i]가 false라면 그것은 i가 소수라는 뜻이다.

v에 i를 넣어준다. 그 다음 i로 만들어지는 모든 소수가 아닌 수의 visited를 true로 만들어준다.

3이 vector에 들어가면 3으로 만들어지는 수 (6, 9, 12...)를 모두 true로 만드는것이다.

이러면 2가 vector에 들어가면 4, 6, 8... 이 모두 true가 되고 3이 vector에 들어가면 6, 9, 12... 이 모두 true가 되고 이를 계속해서 반복해 나가 vector에 모든 소수가 들어가게 된다.

while (true) {
	cin >> n;
	if (n == 0) break;

n을 입력받고 n이 0이면 반복문을 종료시킨다.

bool chk = false;
for (int i = 0; i < v.size(); i++) {
	if (!visited[n - v[i]]) {
		cout << n << " = " << v[i] << " + " << n - v[i] << endl;
		chk = true;
		break;
	}
	if (n - v[i] <= v[i]) break;
}

bool chk는 골드바흐 추측을 체크한다. 만약 추측이 실패하게 되면 chk는 false 상태로 남아있게된다.

vector의 사이즈만큼 반복문을 돌리며

만약 n과 v[i]를 뺀 수가 소수라면

n과 v[i]과 n-v[i]를 출력하고 chk를 true로 바꾼다면 반복문을 종료시킨다.

만약 n - v[i]보다 v[i]가 크다면 반복문에서 그냥 탈출한다.

 

if (!chk) {
	cout << "Goldbach's conjecture is wrong." << endl;
}

만약 chk가 false라면 골드바흐 추측 틀렸다고 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

bool visited[1000001];
vector<int> v;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 3; i <= 1000000; i += 2) {
		if (!visited[i]) {
			v.push_back(i);
			for (int j = i + i; j <= 1000000; j += i) {
				visited[j] = true;
			}
		}
	}
	int n;
	while (true) {
		cin >> n;
		if (n == 0) break;

		bool chk = false;
		for (int i = 0; i < v.size(); i++) {
			if (!visited[n - v[i]]) {
				cout << n << " = " << v[i] << " + " << n - v[i] << endl;
				chk = true;
				break;
			}
			if (n - v[i] <= v[i]) break;
		}
		if (!chk) {
			cout << "Goldbach's conjecture is wrong." << endl;
		}
	}
}

전체코드다.