U E D R , A S I H C RSS

Carmichael Numbers/조현태

느낀점 및 설명

일단 소수이면 안되기 때문에 살포시 저번에 FactorialFactors 에서 사용했던 알고리즘을 사용해서 단시간에 소수인지 확인하도록 하였다.
그리고 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; 
}

저에게 할말

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0103 sec