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

● [문제번호 17103] 골드바흐 파티션

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

● 알아야 할 것

: 에라토스테네스의 체

: 골드바흐의 추측

: vector 자료구조와 메소드

 

● 풀이 과정

: 이전에 있던 골드바흐의 추측 문제에서 조금 변형된 것이다.

https://pirateturtle.tistory.com/185?category=1001702

 

: 에라토스테네스의 체를 구하고

골드바흐의 추측을 이용하지만 두 소수의 조합을 찾았을 때

멈추지말고 갯수를 세면 된다.

 

● 주의 할 것

: 에라토스테네스의 체, 골드바흐의 파티션을 구할 때

반복문의 조건에 주의하여 작성한다.

 

● 참고 할 것

: : 에라토스테네스의 체

2부터 (범위의 끝)의 제곱근까지 각 소수의 배수들을 모두 합성수 처리하면

원하는 범위 내 소수만 남는다.

 

아래 링크에 있는 이미지입니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
int T, N;

// 에라토스테네스의 체 만드는 함수
void check_decimal()
{
    // 기본값 설정
    v[0] = false;
    v[1] = false;
    
    // 2부터 범위의 제곱근까지 반복
    for(int i = 2; i < sqrt(v.size()); i++)
        // 소수인 경우
        if(v[i] == true)
            // 소수의 배수는 합성수로 표시
            for(int j = 2; i * j < v.size(); j++)
                v[i * j] = false;
}

// 골드바흐의 파티션 구하는 함수
int goldbach()
{
    // 기본값 설정
    int cnt = 0;
    
    // 확인하고자 하는 수의 반까지 반복
    for(int n = 2; n < N / 2 + 1; n++)
    {
        // 두 수가 소수인 경우
        if(v[n] == true && v[N - n] == true)
            cnt++;
    }
    
    // 골드바흐 파티션의 수 반환
    return cnt;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 테스트 케이스 입력
    cin >> T;
    
    // 에라토스테네스의 체 만들기 위한 vector
    v.assign(1000001, true);
    
    // 에에에라토스테네스의 체 만들기
    check_decimal();
    
    // 테스트 케이스 반복
    for(int t = 0; t < T; t++)
    {
        // 골드바흐 파티션의 수를 구하고자 하는 수 입력
        cin >> N;
        
        // 골드바흐 파티션의 수 출력
        cout << goldbach() << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [301 - 수학 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9613	GCD 합	https://pirateturtle.tistory.com/189
2	17087	숨바꼭질 6	https://pirateturtle.tistory.com/190
3	1373	2진수 8진수	https://pirateturtle.tistory.com/191
4	1212	8진수 2진수	https://pirateturtle.tistory.com/192
5	2089	-2진수	https://pirateturtle.tistory.com/193
6	17103	골드바흐 파티션	https://pirateturtle.tistory.com/194