[BOJ/백준] 6588 골드바흐의 추측

● [문제번호 6588] 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

● 알아야 할 것

: vector 자료구조와 메소드

: 에라토스테네스의 체

 

● 풀이 과정

: 테스트 케이스의 최댓값인 100만까지의 vector를 만들고

에라토스테네스의 체를 만들어서 소수를 모두 알아둔다.

 

그 다음, N = index + (N - index) 임을 이용하여

index 와 N - index 가 소수인지 판별하여

소수라면 출력후 종료한다.

 

소수가 아니라면 주어진 문자열 출력 후 종료한다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

: 에라토스테네스의 체

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 N;

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

// 골드바흐의 추측 함수
void goldbach()
{
    // 소수는 2부터이니까
    // 2부터 확인하고자하는 수의 반까지
    for(int a = 2; a < N / 2 + 1; a++)
    {
        // 두 수가 소수인 경우
        if(v[a] == true && v[N - a] == true)
        {
            cout << N << " = " << a << " + " << N - a << "\n";
            return ;
        }
    }
    
    // 골드바흐의 추측에 맞지 않는 경우
    cout << "Goldbach's conjecture is wrong.\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 테스트 케이스의 수의 최대값이 100만
    // index를 소수인지 아닌지로 판별하므로 100만 + 1 개로 할당
    v.assign(1000001, true);
    
    // 에에라토스테네스의 체 만드는 함수 호출
    check_decimal();
    
    // 테스트 케이스
    while(1)
    {
        cin >> N;
        
        // 종료    
        if(N == 0)
            break;
        
        // 입력된 N이 골드바흐의 추측에 맞는 수인지 확인하는 함수 호출
        goldbach();
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [300 - 수학 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10430	나머지	https://pirateturtle.tistory.com/180
2	2609	최대공약수와 최소공배수	https://pirateturtle.tistory.com/181
3	1934	최소공배수	https://pirateturtle.tistory.com/182
4	1978	소수 찾기	https://pirateturtle.tistory.com/183
5	1929	소수 구하기	https://pirateturtle.tistory.com/184
6	6588	골드바흐의 추측	https://pirateturtle.tistory.com/185
7	10872	팩토리얼	https://pirateturtle.tistory.com/186
8	1676	팩토리얼 0의 개수	https://pirateturtle.tistory.com/187
9	2004	조합 0의 개수	https://pirateturtle.tistory.com/188