블로그 옮겼습니다

BOJ 1153번 네개의 소수 본문

Algorithm/Problem Solving

BOJ 1153번 네개의 소수

sgc109 2017. 8. 23. 21:05

문제 링크


\( N\le{10^6}\)

자연수 N이 주어진다. N을 네개의 소수의 합으로 분리할 수 있으면 그 네개의 수를 출력하고

불가능하면 -1을 출력하는 문제이다.


우선 골드바흐의 추측이라는 것이 있다. 2보다 큰 짝수는 무조건 두개의 소수의 합으로 나타낼 수 있다는 것이다.

내가 알기론 이미 꽤 큰 수(적어도 PS에서 주어지는 입력의 범위보단 큰 수) 까지는

컴퓨터로 일일이 돌려보아 증명이 되었다고 알고있다. 그러니까 맞다고 생각하고 풀면된다 ㅎㅎ

일단 입력으로 주어진 N이 홀수일 때와 짝수일 때로 나누어 보자.

만약 홀수라면 골드바흐의 추측을 적용하기 위해 이를 짝수로 만들어 줘야 하므로 우선 하나의 수를 빼야하는데

너무 많이 빼면 2이하가 될 수도 있으므로 가장 적게 빼는게 최선이므로 가장 작은 홀수 소수인 3을 빼도록하자

그다음엔 짝수가 되므로 짝수를 유지하면서 뺄 수 있는 가장 작은 소수인 2를 뺀다. 그러면 남는 수는 짝수일 것이다.

그러면 그냥 에라토스테네스의 체로 O(NlglgN) 전처리해놓은 것을 이용하여 소수판별을 하면 O(N)에 나머지 두개를

분리할 수가 있다. 만약 N에서 5를 뺐는데 2보다 크지 않다면 못나누므로 N이 7보다 작거나 같으면 불가능하다.

짝수일 때를 보자. 위와 같은 방법으로 하면 2를 두번뺄 것이다. 그 때 남은 수가 2보다 커야하므로

N이 6보다 작거나 같으면 불가능하다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int N;
int notPrime[1000003];
int main() {
    scanf("%d"&N);
    for(int i = 2; i * i <= N; i++){
        if(notPrime[i]) continue;
        for(int j = i * i ; j <= N; j += i){
            notPrime[j] = 1;
        }
    }
    if(N & 1){
        if(N < 9return printf("-1");
        printf("2 3 ");
        N -= 5;
    }
    else {
        if(N < 8return printf("-1");
        printf("2 2 ");
        N -= 4;
    }
    for(int i = 2; i < N; i++){
        if(!notPrime[i] && !notPrime[N - i]){
            return !printf("%d %d", i, N - i);
        }
    }
    return 0;
}
cs



Comments