백준 17103. 골드바흐 파티션

알고리즘 기초 문제 중 수학1 연습 문제(301)

골드바흐 파티션

1. 간단 설명

---

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다

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

짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구하는 문제

2. 문제 분석

---

두 소수의 순서만 다른 것은 같은 파티션으로 취급한다

즉 8의 골드파흐 파티션인 [3,5]과 [5,3]은 같은 파티션으로 취급한다

예시

5
6
8
10
12
100

입력이 주어졌을 때

6  : [3+3] 1개  
8  : [3+5] 1개 ([5+3]과 같음)
10 : [3+7], [5+5] 1개
12 : [5+7] 1개
100 : [3+97], [11+89], [17+83], [29+71], [41+59], [47+53] 6개

풀이

• 테스트케이스별로 일일히 소수를 구하는것은 비효율적이라 생각하여 에라토스테네스의 체를 이용하여 소수를 구함
• 순서가 다른것은 같은 파티션이므로, 수의 절반까지만 확인하면 된다(n이 최대 100만이므로, 50만까지만 확인)

필요 변수

• 테스트 케이스 개수 T (1<= T <= 100)
• 에라토스테네스의 체를 이용하여 소수를 판별 grid[100만]
• 입력 정수 int n (최대 100만)
• 파티션의 개수 int cnt

주의사항

• 6 = [3+3]처럼 같은 소수가 중복되어 사용되어도 상관없음
• 시간 제한이 0.5초이므로, 약 5억번 수행 가능

알고리즘

1. 에라토스테네스의 체를 초기화한다
2. TC 개수 T입력받기
3. 각 TC에 대하여 아래 작업 수행
	3-1. N 입력받기
	3-2. 2부터 n/2까지 소수를 찾고, n에서 해당 소수를 뺀 값이 소수인지 확인한다
	3-3. 두 값이 소수가 맞다면 카운트 증가
	3-4. 카운트 출력
4. 종료

3. 소스코드

---

#include <iostream>
#include <memory.h>

using namespace std;

bool grid[1000001];

void init_grid() {
	memset(grid, 1, sizeof(grid));
	grid[0] = 0;
	grid[1] = 0;

	for (int i = 2; i <= 1000; i++) { // sqrt(100,0000)
		if (grid[i] == false) continue; 
		for (int j = i*2; j <= 1000000; j = j + i) {
			grid[j] = false;
		}
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	int T, n;

	init_grid();

	cin >> T;
	while (T--) {
		cin >> n;
		int cnt = 0;
		for (int i = 2; i <= n/2; i++) {
			if (grid[i] == true && grid[n - i] == true) cnt++;
		}
		cout << cnt << '\n';
	}


	return 0;
}

시간 제한이 0.5초라서 에라토스테네스의 체를 초기화 하는 과정에서 시간 초과가 나지 않을까 잠깐 고민했다.

그러나, 이전에 풀었던 소수인 펠린드롬 문제에서 배웠던

‘에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 된다’는 사실을 기억했다.

i를 100만번이 아닌 제곱근인 1000번만 수행하여 시간을 2배 이상 단축할 수 있었고,

실제 측정해본 결과 성능에 따라 다르겠지만 시간 내 들어오는 것을 확인할 수 있었다

또한, 메모리 효율을 위해 체를 int형이 아닌 bool형을 사용했음