C언어 223제] 카마이클 수(Carmichael Numbers)

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

 

문제]

암호 알고리즘 중에는 큰 소수를 활용하는 것도 있다. 하지만 어떤 큰 수가 소수인지를 판단하는 것은 그리 쉽지 않다.

페르마 테스트와 같이 빠른 속도로 매우 정확하게 소수 여부를 판단할 수 있는 확률적 소수 테스트 방법이라는 것이 있다. 소수 여부를 판단해야 할 정수 n이 주어졌을 때 a는 2이상 n-1이하의 난수라고 하자. 그러면 다음과 같은 식이 성립하면 n은 소수일 가능성이 있다.

a^n mod m = a

어떤 정수가 이러한 페르마 테스트를 여러 번 통과하면 그 정수는 소수일 가능성이 높다고 할 수 있다. 하지만 안 좋은 소식도 있다. 합성수(소수가 아닌 수) 중에는 그 수보다 작은 모든 정수에 대해 이 페르마 테스트를 통과하는 것도 있다. 이런 수를 카마이클 수라고 부른다.

주어진 정수가 카마이클 수인지 테스트하기 위한 프로그램을 만들어라.

입력
입력은 여러 줄로 구성되며 각 줄에는 작은 양의 정수 n(2<n<65,000)이 입력된다. n=0은 입력의 끝을 나타내며, 그 줄은 처리하지 않는다.


출력
입력된 각 수에 대해 아래에 있는 출력 예에 나와있는 식으로 그 수가 카마이클 수인지 아닌지를 판단한 결과를 출력하라.

입력 예
1729
17
561
1109
431
0

출력 예
The number 1729 is a Carmchael number.
17 is normal.
The number 561 is a Carmchael number.
1109 is normal.
431 is normal.


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제50 카마이클 수(Carmichael Numbers) p195

 

참고풀이]

#include <stdio.h>
#include <stdlib.h>

static char Car[65000];

int Powmod(int a, int b, int n)
{
   //a^b mod n, a<n이라고 가정한다.
   int tmp;

   if(b==0) return 1;
   if(b==1) return a;
   if(b%2)
      return (Powmod(a, b-1,n)*a)%n;
   else
   {
      tmp=Powmod(a, b/2, n);
      return (tmp*tmp)%n;
   }
}

int FermaTest(int a, int n)
{
   return (Powmod(a, n,n)==a);
}

int main()
{
   int i,j,n;

   //카마이클 수를 구한다.
   //n이 소수인지를 구한다.
   //n이 소수가 아닐 경우 2이상 n-1이하의 
   //모든 정수에 대해서 페르마 테스트를 통과하는 지 확인한다. 
   for(i=2;i<65000;i++) 
   {
      if(Car[i]==0)
      {
         Car[i]=2;//소수일 경우 
         for(j=i*2;j<65000;j+=i)
            Car[j]=1;//소수가 아닐 경우 
      }
   }
   for(i=3; i<65000; i++)
   {
      if(Car[i]==1)
      {
         for(j=2;j<i;j++)
            if(!FermaTest(j,i))
            {
               Car[i]=0;
               break;
            }
      }
      else
         Car[i]=0;
   }

   while(scanf("%d",&n), n!=0)
   {
      if(n>=0 && n<65000) 
      {
         if(Car[n])
            printf("The number %d is a Carmchael number.\n",n);
         else
            printf("%d is normal.\n",n);
      }
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

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