C언어 231제] 스미스 수(Smith Numbers)

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

 

문제]

1982년, 앨버트 윌란스키(Albert Wilansky)라는 수학자는 그가 가지고 있던 주소록을 흝어보다가 그의 처제인 H. 스미스(H. Smith)의 전화번호에 특이한 속성이 있다는 것을 발견했다. 그 수의 각 자리 숫자 합은 그 수의 소인수 각 자리 숫자의 합과 같았다. 잘 이해가 안 된다면 실제 숫자를 예로 들어서 생각해보자. 스미스의 전화번호는 493-7775였다. 이 수는 다음과 같이 소인수분해할 수 있다.

4937775 = 3*5*5*65837

전화번호의 각 자리 숫자의 합은 4+9+3+7+7+7+5=42이고, 소인수의 각 자리 숫자의 합은 3+5+5+6+5+8+3+7=42이므로 둘 다 42로 같은 값을 가진다. 윌란스키는 이런 유형의 수에 처제의 이름을 딴, 스미스 수라는 이름을 붙였다.

모든 소수는 이런 속성을 가지기 때문에 소수는 스미스 수에서 제외되었다. 다른 스미스 수로는 6,036과 9,985 등이 있다.

그런데 윌란스키는 그의 처제의 전화번호보다 큰 스미스 수를 찾지 못했다. 윌란스키를 도와서 그 전화번호보다 큰 스미스 수를 찾을 수 있을까?

입력
첫번째 줄에는 테스트 케이스의 개수가 입력된다. 각 테스트 케이스마다 한 줄씩 입력되며, 그 줄에는 10^9보다 작은 양의 정수가 들어있다.

출력
입력된 각각의 값 n에 대해, n보다 큰 가장 작은 스미스 수를 계산해서 그 정수를 출력한다. 한 줄에 하나씩의 결과를 출력한다. 그러한 정수가 반드시 존재한다고 가정해도 된다.

입력 예
1
4937774

출력 예
4937775


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제54 스미스 수(Smith Numbers) p199

 

참고풀이]

#include <stdio.h>

//분해하여 합 구하기 
int nSum(int n)
{
   int na=10;
   int sum=0;

   while(n)
   {
      sum+=n%na;
      n/=na;
   }
   return sum;
}

//소인수 분해하여 합 구하기 
int sisSum(int n)
{
   int na=2;
   int sum=0;

   while(1)
   {
      if(n%na==0)
      {
         if(na<10) sum+=na;
         else sum+=nSum(na);
         n/=na;
         if(n==1) break;
         na=1;
      }
      na++;
   }
   return sum;
}

//소수 여부 체크하기(소수는 제외한다.)
int SosuChk(int n)
{
   int chk=0;
   int na=2;

   if(n!=na)
      for(;na<n;na++)
         if(n%na==0) {chk=1; break;}

   return chk;
}
 

int main()
{
   int T;
   int N;
   int i;

   scanf("%d",&T);
   for(i=1;i<=T;i++)
   {
      scanf("%d",&N);
      while(1)
      {
         N++;
         if(SosuChk(N) && nSum(N)==sisSum(N)) break;
      }
      printf("%d\n",N);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

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