[ICPC] Goldbach's Conjecture(2011 대전 예선)

[ICPC] Goldbach's Conjecture(2011 대전 예선)

Goldbach's Conjecture

골드바흐의 추측(Goldbach's Conjecture)는 오래전부터 알려진 정수론의 미해결 문제이다. 모든 2보다 큰 짝수는 두 개의 소수의 합으로 표시될 수 있다는 것이다. 정의나 이론이 아닌 추측인 이유는 모든 짝수에서 두 소수의 합으로 표현 가능한지는 증명되지 않았기 때문이다.

(참조 - [소수 알고리즘] 소수의 특성과 에라토스테네스의 체 http://ledgku.tistory.com/61)

예를 들어,

$$ 4 = 2 + 2 $$

$$ 6 = 3 + 3 $$

$$ 8 = 3 + 5 $$

$$ 10 = 3 + 7 = 5 + 5 $$

$$ 12 = 5 + 7 $$

$$ 14 = 3 + 11 = 7 + 7 $$

$$ 16 = 3 + 13 = 5 + 11 $$

$$ 18 = 5 + 13 = 7 + 11 $$

$$ 20 = 3 + 17 = 7 + 13 $$

$$ 22 = 3 + 19 = 5 + 17 = 11 + 11 $$

문제

문제 요약

첫 줄에는 입력의 개수가 주어진다. 주어진 짝수는 두 소수의 합으로 표현되는데 한 쌍 또는 여러 쌍의 소수의 합으로 표현되어 질 수 있다. 그 중 두 소수의 차이가 가장 작은 소수 쌍을 찾고 앞에 작은 소수가 오도록 출력한다.

풀이

- 모든 자연수는 단 하나의 소수들의 곱으로 표현된다.

- 소수를 판별하기 위해서는 주어진 자연수의 제곱근까지만 나눠지는지 검사하면 된다.

결론 : 소수 판별하기 위해서는 2~$\sqrt{N}$의 소수들로만 나눠보면 된다.

#include <iostream>
#include <fstream>
#include <cmath>
#include <list>
using namespace std;
 
// 알고리즘
// 1. 입력값 부터 입력값의 제곱근까지의 소수를 구해서 리스트에 저장한다.
// 2. 주어진 자연수가 두개의 소수의 합으로 표현되므로 입력값과 리스트에 저장된 소수의 차가 소수인지 검사하면 된다.
// 3. 가장 차이가 작은 소수 쌍을 찾아야 하므로 리스트의 마지막 부터 검사한다.
 
bool isPrime(int n);
void GoldbachRecursion(list<int> lst, int num, list<int>::reverse_iterator ptr, list<int>::reverse_iterator end);
void GoldbachConjecture(list<int> lst, int num);
 
int main(){
    ifstream inStream;
    inStream.open("input.txt");
    int test_case;
    inStream >> test_case;
 
    for(int t=0; t<test_case; t++){
        int num;
        inStream >> num;
        list<int> lst;
        lst.push_back(2);
        GoldbachConjecture(lst, num);
        lst.clear();
    }
    inStream.close();
    return 0;
}
 
// 입력 값 n이 소수인지 아닌지 확인하는 함수
bool isPrime(int n){
    for(int i=2; i<=sqrt(n); i++){
        if(n%i == 0)
            return false;
    }
    return true;
}
 
// 리스트의 마지막부터 처음까지 진행하며 리스트의 값과 입력값의 차가 소수인지 확인하는 함수
// 소수이면 수를 출력하고 종료한다.
void GoldbachRecursion(list<int> lst, int num, list<int>::reverse_iterator ptr, list<int>::reverse_iterator end){
    if(isPrime(num-(*ptr))){
        cout << *ptr << " " << num-(*ptr) << endl;
        return;
    }
    return GoldbachRecursion(lst, num, ++ptr, end);
}
 
// 입력 값 num의 중간 값까지 소수를 구해 리스트에 저장하고 GoldbachRecursion 함수에 전달해 주는 함수
void GoldbachConjecture(list<int> lst, int num){
    for(int i=3; i<=num/2; i++){
        list<int>::iterator j;
        for(j=lst.begin(); j != lst.end(); j++){
            if(i % (*j) ==0)
                break;
        }
        if(j==lst.end()){
            lst.push_back(i);
        }
    }
    
    list<int>::reverse_iterator ptr = lst.rbegin();
    list<int>::reverse_iterator end = lst.rend();
    
    return GoldbachRecursion(lst, num, ptr, end);
}

결과