Follows 10006.c (Total 63 lines):

/* @JUDGE_ID:4461XX 10006 C */
/* A */
#include<stdio.h>
#include<string.h>
#define MAX_N 65000

char isprime[MAX_N] ;/*0->not prime && don't know if it is a carmichael number*/
                     /*1->is prime or not carmichael number*/
                     /*2->is carmichael number*/
long long int N ;
void make_primetable( void )
{
	int i , j ;
	
	memset( isprime , 1 , sizeof( isprime ) ) ;
	for( i=2 ; i<MAX_N ; i++ )
		if( isprime[i] )
			for( j=2 ; i*j<MAX_N ; j++ ) isprime[i*j] = 0 ;
}
long long int pow( long long int a , long long int n )
{
	long long int tmp ;
	
	if( n==1 ) return a%N ;

	tmp = pow( a , n/2 ) ;
	tmp = ( tmp * tmp ) % N ;

	if( n%2 ) return ( a * tmp ) % N ;
	else return tmp ;
	
}
int IsCarmichael( void )
{
	long long int a ;

	for( a=2 ; a<N ; a++ )
		if( pow( a , N )%N!=a ) return 0 ;

	return 1 ;
}
int main( void )
{
	make_primetable() ;
	while( scanf( "%lld" , &N )==1 ){
		if( !N ) break ;

		if( !isprime[N] )
			if( IsCarmichael() ){
				printf( "The number %lld is a Carmichael number.\n" , N ) ;
				isprime[N] = 2 ;
			}
			else{
				printf( "%lld is normal.\n" , N ) ;
				isprime[N] = 1 ;
			}
		else if( isprime[N]==1 ) printf( "%lld is normal.\n" , N ) ;
		else if( isprime[N]==2 ) printf( "The number %lld is a Carmichael number.\n" , N ) ;
	}

	return 0 ;
}
/* @END_OF_SOURCE_CODE */

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com