골드바흐 파티션 (feat. 백준, 17103번)

골드바흐 파티션
https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    cin >> N;
    bool arr[1000001]{false};
    arr[0] = arr[1] = true;
    register int e = sqrt(1000000);
    for(register int i = 2, j; i <= e; ++i)
        if(!arr[i])
            for(j = i << 1; j <= 1000000; j += i)
                arr[j] = true;
    for(register int n = 0, i, v, ans; n < N; ++n){
        ans = 0;
        cin >> v;
        for(i = 2; i < v; ++i)
            if(!arr[v - i] && !arr[i]){
                ++ans;
                if(v - i == i)
                    ++ans;
            }
        cout << (ans >> 1) << "\n";
    }
	return 0;
}
// *&)*@*

 

반응형

1. 시간 초과로 인해 생각을 해야했던 문제입니다.
2. 두 소수로 X를 표현할때, 소수 A와 B가 서로 대칭되더라도 1개로 카운팅해야 하므로 애초에 모두 카운팅하고 2로 나누었습니다.
3. 2번의 경우, A와 B가 같은 경우는 일부러 +1을 카운팅해야 하므로 이점을 유의해야 합니다.
4. 두 소수가 X가 되는지는 2 (소수의 시작) 와 X - 2 (X를 만들 수 있는 마지막 소수) 를 검사하며 점점 가운데로 좁혀가면 되겠습니다. (투포인터로 구해도 되지만 0.5초에 걸립니다.)