[백준 17103번 C++] 골드바흐 파티션

17103번: 골드바흐 파티션 (acmicpc.net)

17103번: 골드바흐 파티션

이전에 푼 골드바흐 추측 문제들과 매우 유사하다. 

테스트 케이스의 개수만 세어주면 되는 문제!

    for(int j=0; j<T; j++){
        cin >> n;
        int count = 0;
        
        for(int i=2; i<=n/2; i++){
            if(arr[i] && arr[n-i]){
                count++;
            }
        }
        
        cout << count << "\n";
    }

입력받는 것을 for문으로 바꾸어주고, count 변수를 통해서 테스트 케이스 쌍을 찾을 때마다 1씩 증가하게 했다. 

for문의 범위도 int i=2 부터 i<=n/2일 때까지로 수정했다.

절반을 넘어가면 위치만 바뀌고 똑같아지니까!

증가도 i+=2에서 i++로 수정했다. 

 

그렇게 나온 최종 코드는

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T, n;
    cin >> T;
   
    vector<bool> arr(1000001, true);
    arr[1] = false; 
    
    for(int i=2; i*i <=1000001; i++){
        if(arr[i]==false) continue;
        for(int j = 2*i; j<=1000001; j+=i){
            if(arr[j]==false) continue;
            else arr[j] = false;
        }
    }
    
    for(int j=0; j<T; j++){
        cin >> n;
        int count = 0;
        
        for(int i=2; i<=n/2; i++){
            if(arr[i] && arr[n-i]){
                count++;
            }
        }
        
        cout << count << "\n";
    }
    
    return 0;
}