[BOJ/백준][Gold4] 1153 : 네 개의 소수 (C++)

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

1153번: 네 개의 소수

 

[난이도] Gold4
[유형] 정수론

[풀이]
골드바흐의 추측이라는 정수론 개념을 이용해서 풀어야 하는 문제이다.
https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

일단 시간내에 소수를 구하기 위해 에라토스테네스의 체를 이용해 소수를 미리 구해준다.

골드바흐의 추측 : '2보다 큰 모든 짝수는 두 소수의 합으로 표현가능하다'

4개 소수의 합으로 표현하기 위해서 N은 무조건 8보다는 커야 한다.
N이 홀수인 경우, N에서 2,3을 빼주어서 짝수를 만든 뒤 N-5를 두개의 소수로 만들 수 있는 짝을 찾는다.
N이 짝수인 경우, N에서 2,2를 빼준 뒤에 N-4를 두개의 소수로 만들 수 있는 짝을 찾는다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N;
bool a[1000001];
int main(){
    scanf("%d",&N);
    a[0]=a[1]=1;
    for(int i=2;i<=N;i++){
        for(int j=2*i;j<=N;j+=i) a[j]=1;
    }
    vector<int> ans;
    if(N<8) puts("-1");
    else{
        if(N%2){
            ans.push_back(2);
            ans.push_back(3);
            for(int i=2;i<=N;i++){
                if(!a[i] && !a[N-5-i]){
                    ans.push_back(i);
                    ans.push_back(N-5-i);
                    break;
                }
            }
        }else{
            ans.push_back(2);
            ans.push_back(2);
            for(int i=2;i<=N;i++){
                if(!a[i] && !a[N-4-i]){
                    ans.push_back(i);
                    ans.push_back(N-4-i);
                    break;
                }
            }            
        }
    }
    for(auto p : ans) printf("%d ",p);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1153.cpp