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

17103번: 골드바흐 파티션

---

반응형

📌 접근 방법

✔ 에라토스테네스의 체(Sieve of Eratosthenes)

• 소수를 효율적으로 찾아내는 알고리즘
• 큰 범위의 소수를 빠르게 구할 수 있음
• 시간 복잡도 : O(n log log n)
• 참고 링크

동작과정

1. 2부터 시작하여 소수인 숫자를 찾음
2. 현재 소수인 숫자를 제외한 그의 배수들을 모두 제거함
3. 다음으로 넘어가서 아직 제거되지 않은 가장 작은 숫자를 찾고, 해당 숫자를 소수로 간주함
4. 위의 과정을 반복하여 소수를 찾아냄

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;
int arr[1000001]={0};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin>>T;

    for(int i=2; i<1000000; i++){
        arr[i]=i;
    }
    for(int i=2; i<1000000; i++){
        if(arr[i]==0)continue;
        else{
            for(int j=i*2; j<=1000000; j+=i){
                arr[j]=0;
            }
        }
    }
    while(T>0){
        int x;
        cin>>x;
        int a, sum=0;
        for(int i=2; i<=x; i++){
            a=i;
            if(x==(arr[a]+arr[x-a])){
                sum++;
                if(arr[a]==arr[x-a]){
                    sum++;
                }
            }
        }
        cout<<sum/2<<'\n';
        T--;
    }


    return 0;
}