하루하루 꾸준히, 인생은 되는대로

알고리즘

백준 14905 C언어

긤효중 2022. 2. 20. 20:31

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

 

14905번: 소수 4개의 합

모든 자연수를 4개의 소수의 합으로 나타낼 수 있을까? 이 물음에 대한 답은 '8 이상의 모든 자연수에 대해 그렇다'이지만, 데이빗은 그 사실을 알지 못했다. 데이빗은 프로그램을 돌려 4개의 소

www.acmicpc.net


문제

모든 자연수를 4개의 소수의 합으로 나타낼 수 있을까? 이 물음에 대한 답은 '8 이상의 모든 자연수에 대해 그렇다'이지만, 데이빗은 그 사실을 알지 못했다. 데이빗은 프로그램을 돌려 4개의 소수의 합으로 표현할 수 없는 수를 찾아내 보기로 했다. 소수는 "두 개의 다른 자연수로만 나눠 떨어지는 자연수"이다. 예를 들어, 37은 37과 1로만 나눠 떨어지므로 소수이다


입력

입력 파일에는 한 줄에 하나씩 1 이상 100,000,000 이하의 자연수가 주어진다.


출력

입력 라인에 맞춰, 주어진 조건에 맞는 4개의 소수를 한 줄에 출력한다. 입력된 수가 소수 4개의 합으로 표현될 수 없으면 “Impossible.”이라 출력한다. 답은 여러 개가 있을 수 있다. 하지만 더해서 입력된 수가 나오는 소수 4개라면 모두 정답이다.


해결방안: 골드바흐의 추측을 이용하자. 8이상의 자연수일때 짝수이면 2 + 2+ A + B의 형태로 나타낼 수 있다.

예를 들어 14일때 2 + 2 + 5 + 5 (모두 소수) or 2 + 2 + 3 + 7(모두 소수) 이런식으로 2 + 2 + 소수 + 소수의 형태로 8이상의 짝수를 모두 표현 할 수 있다.

 

그리고 홀수 일때는 2 + 3 + 소수 + 소수의 형태로 표현 가능하다. 

예를 들어 15일때 2 + 3 + 5 + 5(모두 소수)이런식으로 짝수,홀수를 분기로 나눠서 계산하면 된다.

그리고 에라토스테네스의 체를 통해 1차적으로 소수를 판별해준다.


전체 소스 코드->

#include <stdio.h>
#include <math.h>
#define LEN 100000000
//백준 14905번

 

int array[LEN];
int Lprime = 0;
int Rprime = 0;
 
void Push(){ //에라토스테네스의 체로 소수 판별
 
    for(int i = 2;i<=sqrt(LEN);i++){
        array[i] = i;
    }
    for(int i = 2;i<=LEN;i++){
        if(array[i] == 0){
            continue;
        }
        for(int j = i+i;j<=LEN;j=j+i){
            array[j] = 0;
        }
    }
}
 
int Prime_Calculate(int n){
 
    Lprime = 0;
    Rprime = 0;
 
    if(n<8){
        return -1; //8보다 작으면 -1리턴
    }
 
   else if(n%2 == 0){ //짝수일때  n = 2 + 2 + a + b의 형태로 나타낼 수 있어서 n-4 = a + b, n을 -4 하고 골드바흐의 추측으로 합이 n이 되는 소수를 찾자
      int N = n-4;
       for(int i = N/2;i>=2;i--){
           if(array[i] + array[N-i] == N){
               Lprime = array[i];
               Rprime = array[N-i];
               return 2; //짝수일때 2리턴
           }
       }
   }
    else if(n%2 != 0){//홀수일때 n = 2 + 3 + a + b의 형태로 표현가능하다. n-5 = a+b, n을 -5하고 골드바흐의 추측으로 합이 n이되는 소수를 찾자
        int N = n-5;
        for(int i = N/2;i>=2;i--){
            if(array[i] + array[N-i] == N){
                Lprime = array[i];
                Rprime = array[N-i];
                return 3; //홀수일때 3리턴
            }
        }
    }
    return -1;//그 외에는 -1리턴
}
 
int main(void){
 
    Push();
   int x;
    while(scanf("%d",&x)!= EOF){ //x가 EOF가 아닐때까지
 
       
        if(Prime_Calculate(x) == -1){ //-1이면 소수 4개의 합으로 나타낼 수 없다->Impossible출력
            printf("Impossible.\n");
        }
        else{ //2이면 짝수인경우
           if(Prime_Calculate(x) == 2){
             printf("2 2 %d %d\n",Lprime,Rprime);
           }
            else if(Prime_Calculate(x) == 3){ //3이면 홀수인 경우
                printf("2 3 %d %d\n",Lprime,Rprime);
            }
        }
     
 
 
    }
}

 

'알고리즘' 카테고리의 다른 글

백준 14921 C언어  (0) 2022.02.25
백준 1316 C언어  (0) 2022.02.23
백준 1475 C언어  (0) 2022.02.19
백준 1448 C언어  (0) 2022.02.17
분할정복  (0) 2022.02.15