C언어 230제] 소수 네 개의 합(Summation of Four Primes)

출처 : 반크_반크 20년 백서

 

문제]

워링(Waring)의 소수 가설은 모든 홀수는 소수 또는 소수 세 개의 합이라고 주장하는 가설이다. 골드바흐(Goldbach)의 가설은 모든 짝수는 소수 두 개의 합이라고 주장하는 가설이다. 이 두 문제는 200년이 넘게 해결되지 않고 있다.

이 문제와 관련하여 조금 간단한 문제를 풀어보자. 주어진 정수를 정확하게 소수 네 개의 합으로 표현하는 방법을 찾아내자.

입력
한 줄에 하나씩의 정수 n(N<=10000000)이 입력된다. 입력은 파일 끝 문자에 의해 종료된다.

출력
각 입력 케이스 n에 대해 합해서 n이 되는 네 개의 소수를 출력한다. (한 줄에 한 케이스) 입력된 수가 소수 네 개의 합으로 표현될 수 없으면 "Impossible"이라고 출력한다. 답이 여러 가지 나올 수도 있는데, 그런 경우에는 아무 답이나 출력해도 된다.

입력 예
24
36
46

출력 예
3 11 3 7
3 7 13 13
11 11 17 7


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어)]

문제53 소수 네 개의 합(Summation of Four Primes) p198

 

참고풀이1]

#include <stdio.h>
int SoSu[10000000];

void SoSu_Ruslt(int NN)
{
   int i,j;

   SoSu[2]=1;
   for(i=3;i<=NN;i+=2)
   {
      for(j=2;j<i;j++)
         if(i%j==0) break;
      if(j==i) SoSu[i]=1;
   }
}

int main()
{
   int N;
   int cnt;//소수의 개수를 센다.
   int Sum;//소수의 합을 구한다.
   int nSo[4];//소수를 넣을 배열변수 
   int i,j,k,l;

   while(scanf("%d",&N) != EOF)
   {
      if(N<=10000000)
      {
         SoSu_Ruslt(N);
         cnt=0;
         if(N>=8)
         {
            for(i=2;i<N;i++)
            { 
               Sum=0;
               if(SoSu[i]) nSo[0]=i; 
               for(j=2;j<N;j++)
               {
                  if(SoSu[j]) nSo[1]=j;
                  for(k=2;k<N;k++)
                  {
                     if(SoSu[k]) nSo[2]=k;
                     for(l=2;l<N;l++)
                     {
                        if(SoSu[l]) nSo[3]=l;

                        if(N==(nSo[0]+nSo[1]+nSo[2]+nSo[3]))
                        {
                           for(j=0;j<4;j++) printf("%d ",nSo[j]);
                           printf("\n");
                           cnt=1;
                           break;
                        }
                        cnt=0;
                     }
                     if(cnt) break;
                  }
                  if(cnt) break;
               }
               if(cnt) break;
            }
         }
         if(!cnt) printf("Impossible\n");
      }
   }
   return 0;
}

 

 

참고풀이1 결과]

 

 

참고풀이2]

#include <stdio.h>
#include <math.h>
#define MaxN 10000000

static int N, Sum, Se[4];

int isPrime(int a) //소수여부를 체크 
{
   int i;

   if(a<2) return 0;
   for(i=2;i<=sqrt(a); i++)
      if(a%i==0) return 0;

   return 1;
}

//N이 8이상인 경우 언제나 해가 존재한다.
int PrimeSum(int a) 
{
   int i;
   if(a<0)
   {
      if(Sum==N) return 1;
      return 0;
   }
   for(i=N-Sum-2*a;i>=2; i--)
      if(isPrime(i))
      {
         Se[a]=i;
         Sum+=i;
         if(PrimeSum(a-1)) return 1;
         Sum-=i;
      }
   return 0;
}

int main()
{
   int i;

   while(scanf("%d",&N) != EOF)
   {
      Sum=0;
      if(PrimeSum(3))
         for(i=0;i<4;i++) printf("%d ",Se[i]);
      else
         printf("Impossible");
      printf("\n");
   }

   return 0;
}

 

참고풀이2 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 여름