골드바흐의 추측

문제

백준 9020번 - 골드바흐의 추측

언어

JavaScript

순서도

에라토스테네스의 체를 이용해서 10,000 이하의 소수를 모두 구하기
주어진 입력에 대해서 골드바흐 파티션 구하기
출력 양식에 맞게 출력

문제 풀이 step 1

백준 1929번 - 소수 구하기 풀이 에서 사용했던 에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 문제입니다.
에라토스테네스의 체에 대해서 다시 알아보자면,
- 10000 이하의 소수를 구한다고 하면 1 ~ 10000 을 적습니다.
- 1 은 소수가 아니므로 지웁니다.
- 지워지지 않은 수 중에서 가장 작은 수는 2 입니다. 2 는 소수이고, 2 의 배수는 모두 소수가 아니므로 지웁니다.
- 그 다음 지워지지 않은 수 중에서 가장 작은 수는 3 입니다. 3 도 소수이고, 3의 배수는 모두 소수가 아니므로 지웁니다.
- 위의 과정을 반복하며 배수의 성질을 이용해서 소수가 아닌 수는 모두 지웁니다.

문제 풀이 step 2

소수를 구했으면, 이제 골드바흐 파티션을 구하면 됩니다.
- 골드바흐 파티션은 2 보다 큰 짝수를 두 개의 소수의 합으로 표현하는 것을 말합니다. (ex. 12 = 5 + 7)
그리고 먄약 골드바흐 파티션이 여러 가지인 경우 두 소수의 차이가 가장 작은 것을 출력해야 합니다.
따라서 우선 주어진 수에 대해서 가운데 값을 구합니다.
그리고 그 가운데 값을 1 씩 줄여가면서 골드바흐 파티션을 구합니다.
- 예를 들어 주어진 n 이 16 이라고 한다면, 가운데 값은 8 입니다.
- 8 은 소수가 아닙니다. 그리고 8 (16 - 8) 도 소수가 아닙니다.
- 7 은 소수입니다. 하지만 9 (16 - 7) 은 소수가 아닙니다.
- 6 은 소수가 아닙니다. 그리고 10 (16 - 6) 도 소수가 아닙니다.
- 5 는 소수입니다. 그리고 11 (16 - 5) 는 소수입니다.
- 따라서, 5 와 11 이 골드바흐 파티션이 됩니다.
위 과정을 통해서 골드바흐 파티션을 구하고 출력 양식에 맞게 출력해주면 정답이 됩니다. (출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분)
추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const getGoldbachPartition = (isPrime, n) => {
	let [left, right] = [null, null];

	// 반복문의 초기값은 가운데 값인 n / 2
	for (let i = parseInt(n / 2); i >= 2; i--) {
		// i 와 n - i 가 소수라면 골드바흐 파티션임
		if (isPrime[i] === true && isPrime[n - i] === true) {
			[left, right] = [i, n - i];
			break;
		}
	}

	return `${left} ${right}`;
};

const solution = (input) => {
	const MAX = 10001;
	let t = Number(input[0]);

	// 에라토스테네스의 체를 이용해서 10000 이하의 소수를 구한다.
	const isPrime = Array(MAX).fill(true);
	isPrime[0] = isPrime[1] = false;
	for (let i = 2; i < MAX; i++) {
		if (isPrime[i] === false) continue;

		for (let j = i + i; j < MAX; j += i) {
			isPrime[j] = false;
		}
	}

	let res = "";
	let index = 1;
	while (t-- > 0) {
		const n = input[index++];

		// 출력 양식에 맞게 문자열 구성
		res += `${getGoldbachPartition(isPrime, n)}\n`;
	}

	return res;
};

console.log(solution(input));