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 2021-02-07 05:22:49
Processing time 0.0228 sec