C언어 227제] 팩토리얼 나누기(Factovisors)

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

 

문제]

팩토리얼 함수 n!은 모든 음이 아닌 정수 n에 대해 다음과 같이 정의된다.
0!
n!=nX(n-1)! (n>0)
다음과 같은 식을 만족하는 정수 k가 존재하면 b가 a로 나뉘어 떨어진다. (a divides b)고 한다.
kXa=b

입력
입력은 여러 줄로 구성되며 각 줄에는 두 개의 음이 아닌 정수 n과 m이 입력된다. n과 m은 모두 2^31보다 작다.

출력
입력된 각 줄에 대해 n!이 m으로 나뉘어 떨어지는 지를 나타내는 문장을 출력한다. 문장의 형식은 아래에 나와 있는 형식대로 한다.

입력 예
6 9
6 27
20 10000
20 100000
1000 1009

출력 예
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 52 팩토리얼 나누기(Factovisors) p197

 

참고풀이]

#include <stdio.h>
static int check[46341], pn, prime[5000];

//소수를 구한다. 
void checkprime()
{
   int i, j;
   for(i=2;i<46341;i++)
   {
      if(check[i]) continue;
      check[i]=i;
      prime[pn++]=i;
      for(j=i+i;j<46341;j+=i) check[j]=-1;
   }
}

int main()
{
   int n, m;
   int i, j, d, k, k2;
   int chk;

   checkprime();

   while(scanf("%d%d",&n,&m) != EOF)
   {
      if(m==0)
         chk=0;
      else if (m==1 || n>=m)
         chk=1;
      else
      {
         chk=1;
         //팩토리얼을 구한다.
         d=m;
         for(i=0;i<pn&&chk;i++)
         {
            k=0;
            while(d%prime[i]==0)
            {
               k++;
               d/=prime[i];
            }

            k2=0;
            for(j=prime[i];k2<k;j+=prime[i])
            {
               k2+=n/j;
               if(n/j<prime[i]) break;
            }
            if(k2<k) chk=0;
            if(d==1) break;
         }
         if(d>n) chk=0;
      }

      //결과값을 출력한다.
      if(chk)
         printf("%d divides %d!\n",m,n);
      else
         printf("%d does not divides %d!\n",m,n);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

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