백준 17103 골드바흐 파티션

작성일 | In |

Problem : 골드바흐의 파티션

유형 : 수학

문제 설명

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

예제 입력

1
2
3
4
5
6
5
6
8
10
12
100

예제 출력

1
2
3
4
5
1
1
2
1
6

해결 전략

에라토스 테네스의 체를 이용하여 소수를 구하고 이용한다.

앞뒤만 바뀐 경우를 방지하기 위해서, 절반 까지만 탐색한다.

주의할 점

  • 두 소수의 순서만 다른 것은 같은 파티션이다.

풀이

소수 테이블을 만든다.

  • 에라토스 테네스의 체를 이용하여 소수를 구한다.

골드바흐의 추측이 적용되는 파티션을 구한다.

  • a, b가 n을 구성하는 소수라고 할때, a은 n 이하까지만 탐색한다.
    • 10을 예시로 볼때, (3 , 7), (5 , 5) 가 가능하고, (7 , 3)이 가능하다.
    • 하지만 (7, 3)은 중복되었기 때문에 제외 해줘야 한다.
    • 처음 숫자인 a의 범위를 10의 1/2인 5 이하로 탐색을 해주면된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define MAX 1000001

int visit[MAX], t;
using namespace std;

void prime_set() {
    for (int i = 2; i < MAX; ++i) {
        for (int ii = i; ii < MAX; ii += i) {
            visit[ii]++;
        }
    }
}

int solve(int n) {
    int partition = 0;
    for (int i = 3; i <= n / 2; i += 2) {
        if (visit[i] != 1 or visit[n - i] != 1)continue;
        partition++;
    }
    return partition;
}

void input() {
    cin >> t;
    int n;
    while (t--) {
        cin >> n;
        cout << solve(n) << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    prime_set();
    input();
    return 0;
}

피드백

없음