[C++]9020번: 골드바흐의 추측

주어진 값 범위 내에서 소수를 구하고, 주어진 값에서 소수를 뺀 값도 소수인지 검사하는 방식으로 생각했다.

다만 골드바흐 파티션이 여럿이라면 이 값의 차이가 가장 적은 것을 반환해야 한다.

작은 숫자부터 검사하게 되면 골드바흐 파티션을 찾았더래도 차잇값이 더 작은 파티션을 찾기 위해 계속 반복문을 진행해야 할 것이다.

그래서 범위 내 소수 검사를 값이 큰 것부터 내림차순으로 진행하도록 바꿔보기로 했다.

 

예를 들어, 16이 주어졌다면 소수 검사는 2부터 16/2=8까지만 내림차순으로 진행한다. (덧셈이기때문에 /2 범위)

그러면 7 5 3 2의 값이 나온다. 7부터 내림차순으로 16에서 뺀 값이 소수인지 검사한다는 의미.

 

Prime 검사 함수는 이전에 쓴 것을 그대로 사용했다.

int main(int argc, char* argv[]) {
    int n, a;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a;
        for(int j = a/2; j >=2; j--) {
            if(isPrime(j)) {
                if(j+j == a || isPrime(a-j)) {
                    cout << j << " " << a-j << '\n';
                    break;
                }
            }
        }
    }
    return 0;
}

 

j+j==a인지도 or 조건으로 확인하게 한 것은, 10의 경우를 생각하면 되겠다. isPrime(5)을 한번 더 돌리느니, 5+5==10인지 검사하는 게 더 빠르지 않을까?