/*------------------------------------------------------------------------------
 * problem018.c: Carmichael Numbers (7.6.2)
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

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

/*------------------------------------------------------------------------------
 * Type Definitions
**----------------------------------------------------------------------------*/

typedef unsigned int uint;

/*------------------------------------------------------------------------------
 * Constants 
**----------------------------------------------------------------------------*/

#define MAX_INT	65000
#define	TRUE	1
#define FALSE	0

/*------------------------------------------------------------------------------
 * Globals
**----------------------------------------------------------------------------*/

static int Prime[MAX_INT + 1];

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static void
compute_primes(int n)
{
    int i, j;
    
    for (i = 0; i < n; i++)
	Prime[i] = TRUE;

    for (i = 2; i < n; i++) 
	for (j = 2; j < n && (i * j) < n; j++) 
	    Prime[i * j] = FALSE;
}

static uint
compute_fermat(uint a, uint p, uint n)
{
    uint r;

    if (p == 1)
	return (a);

    r = compute_fermat(a, p / 2, n);
    r = (r * r) % n;

    if (p % 2)
	r = (r * a) % n;

    return (r);
}

static int
is_fermat(uint a, uint n)
{
    return (compute_fermat(a, n, n) == a);
}

static int
is_carmichael(uint n)
{
    uint i;

    if (Prime[n])
	return (FALSE);

    for (i = 2; i < n; i++)
	if (!is_fermat(i, n))
	    return (FALSE);

    return (TRUE);
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    uint i;

    compute_primes(MAX_INT);

    while (scanf("%u", &i) != EOF) {
	if (i == 0) break;

	if (is_carmichael(i))
	    printf("The number %u is a Carmichael number.\n", i);
	else
	    printf("%u is normal.\n", i);
    }
    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/