[백준/BOJ] 17103번 골드바흐 파티션 (C/C++)

백준 온라인 저지(BOJ) 17103번 골드바흐 파티션

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

17103번: 골드바흐 파티션

* 사용언어 : C언어, C++

 

1. 문제

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 함

각 테스트 케이스 별 입력 N의 골드바흐 파티션 수를 출력

 

2. 풀이

우선 에라토스테네스의 체를 활용하여 1부터 1,000,000까지 소수 여부를 구합니다.

 

에라토스테네스의 체를 사용할 때 for문의 max값은

1,000,000이 아닌 1,000(루트 1,000,000)까지 진행하면 됩니다. 

[에라토스테네스의 체 사용 시 루트 n까지만 진행해도 되는 이유]
만약 어떤 수 n이 1과 n이 아닌 다른 수로 나누어 떨어진다면 n은 a * b로 표현할 수 있습니다.
이 때 a가 루트 n보다 크거나 같다면, b는 루트 n보다 작거나 같게 됩니다.

따라서 루트 n보다 작은 b만으로 에라토스테네스의 체를 사용하더라도
n 이하의 모든 소수가 아닌 수를 잡아낼 수 있게 됩니다.

 

이후 골드바흐 파티션을 찾아 cnt를 늘려주는데,

중복을 허용하지 않으므로 소수 확인은 i = 2부터 n / 2까지만 반복합니다.

([i]와 [N - i] 둘 다 소수인 경우에만 +1)

 

N이 10일 때를 예시로 살펴보면 아래와 같은데,

N / 2(이 경우 5)까지만 count를 해야 중복이 포함되지 않습니다.

(7, 3)은 (3, 7)과 중복

 

참고로 구동 시간을 조금이라도 줄이려고 비트 연산자를 사용했는데,

비트 연산자 대신 나누기, 등호, && 연산을 사용해도 통과가 됩니다.

 

[주석 처리한 코드(52ms) → bitwise 사용 코드(28ms)]

// n_half = n / 2;
n_half = n >> 1;

for (int i = 2; i <= n_half; ++i) {
	// if (isNotPrime[i] == 0 && isNotPrime[n - i] == 0) ++cnt;
	if (!isNotPrime[i] & !isNotPrime[n - i]) ++cnt;
}

 

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
17103_골드바흐 파티션
5016KB	28ms
*/
#include <cstdio>
#include <math.h>

const int LM = 1000000 + 1;
const int RLM = sqrt(LM) + 1;
int isNotPrime[LM], t, n;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int idx, cnt, n_half;

	isNotPrime[1] = 1;
	for (int i = 2; i < RLM; ++i) {
		if (isNotPrime[i]) continue;
		idx = i * 2;
		while (idx < LM) {
			isNotPrime[idx] = 1;
			idx += i;
		}
	}

	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		cnt = 0;
		n_half = n >> 1;

		for (int i = 2; i <= n_half; ++i) {
			if (!isNotPrime[i] & !isNotPrime[n - i]) ++cnt;
		}
		printf("%d\n", cnt);
	}
	return 0;
}