느낀점 및 설명 ¶
일단 소수이면 안되기 때문에 살포시 저번에 FactorialFactors 에서 사용했던 알고리즘을 사용해서 단시간에 소수인지 확인하도록 하였다.
그리고 CarmichaelNumbers가 뭔지 몰라서..인터넷에서 뒤져본 결과 최소 3개 이상의 소수의 곱이었던 관계로 그 부분도 추가해 주었다.
마지막으로.. 심심 하면 새침한 표정으로 나타나는 변수크기 초과오류 아가씨..
이 아가씨를 달래기 위해.. 그간 굴리지 않아서 녹이써서 안돌아가는 머리를 굴려 약간의 수학적 계산을 동원해서..
아가씨가 입을 수 있는 크기의 숫자가 나머지로 나오도록 해주었다. 다행히 주어진 숫자의 범위가 크지않아 예쁜 숫자들의 범위에서 끝났다고나 할까..
대신 연산이 느려지긴 했겠지만 뭐.. 범위가 작은 관계로 입력하면 바로바로 나와주는 쎈쓰~! 그래서 별로 신경쓰지는 않았다.
이정도면 충분 하려나.. 그럼 좋은하루!!^^*
그리고 CarmichaelNumbers가 뭔지 몰라서..인터넷에서 뒤져본 결과 최소 3개 이상의 소수의 곱이었던 관계로 그 부분도 추가해 주었다.
마지막으로.. 심심 하면 새침한 표정으로 나타나는 변수크기 초과오류 아가씨..
이 아가씨를 달래기 위해.. 그간 굴리지 않아서 녹이써서 안돌아가는 머리를 굴려 약간의 수학적 계산을 동원해서..
아가씨가 입을 수 있는 크기의 숫자가 나머지로 나오도록 해주었다. 다행히 주어진 숫자의 범위가 크지않아 예쁜 숫자들의 범위에서 끝났다고나 할까..
대신 연산이 느려지긴 했겠지만 뭐.. 범위가 작은 관계로 입력하면 바로바로 나와주는 쎈쓰~! 그래서 별로 신경쓰지는 않았다.
이정도면 충분 하려나.. 그럼 좋은하루!!^^*
소스 ¶
~cpp
#include <stdio.h>
#include <iostream>
const int MINIMUM=2;
const int MAXIMUM=65000;
int Carmichael(int);
int Sosu(int);
void main()
{
while (1)
{
printf("숫자를 입력해 주세요.\n");
int number=-1;
int answer=0;
while ((0!=number)&&(number<MINIMUM || MAXIMUM<number))
scanf("%d",&number);
if (0==number)
break;
answer=Carmichael(number);
if (0==answer)
printf("%d is normal.\n",number);
else
printf("The number %d is a Carmichael number.\n",number);
}
}
int Carmichael(int number)
{
if (0!=Sosu(number))
return 0;
for (register int i=2; i<number; ++i)
{
unsigned int a=1;
for (register int j=0; j<number; ++j)
{
a*=i;
a%=number;
}
if (i!=a)
return 0;
}
return 1;
}
int Sosu(int number)
{
if (2==number || 3==number)
return 1;
int *log_number=(int*)malloc((number+2)*sizeof(int));
int gab;
log_number[2]=1;
log_number[3]=0;
for (register int i=4; i<=number;i+=2)
{
log_number[i]=1;
log_number[i+1]=0;
}
for (register int i=3; i<=number; ++i)
{
if (0==log_number[i])
{
if (i==number)
{
free(log_number);
return 1;
}
log_number[i]=1;
gab=i+i;
for(register int j=i+gab; j<=number; j+=gab)
++log_number[j];
}
}
if (log_number[number]<3)
{
free(log_number);
return 2;
}
free(log_number);
return 0;
}
