Description

Once again, agent Charles Carmichael [1] has been captured by the rogue enemy spies. Fortunately, he has left clues about his location with the Nerd Herd at the Buy More [2]. Being the geek that he is though, agent Carmichael has encoded his information as a series of numbers.

Your mission as a top secret data analyzer is to crack the code! Being the clever and handsome programmer that you are, you have figured out that the stream of integers contains a particular type of numbers: Carmichael numbers! These are composite numbers (non-primes) that pass the following prime test for all numbers smaller than n:

a^n mod n = a   // Fermat test

That is let a be a random number between 2 and n - 1, where n is the number we are testing. n is probably a prime if it passes the Fermat test several times. As noted, however, there are some composite (non-primes) that also pass this test for all numbers less than n. These numbers, of course, are called Carmichael numbers and your job is to help agent Walker [3] filter the list of numbers and determine which ones are Carmichael numbers.

Input

The input will consist of a series of lines, each containing a small positive number n where (2 < n < 65,000). A number n = 0 will mark the end of the input and should not be processed. Here is a sample input:

1729
17
561
1109
431
0

Output

For each number in the input, print whether it is a Carmichael number or not as shown in the sample output. Here is a sample output:

The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

[1]	Chuck Bartowski.

[2]	If teaching this class doesn't work out, I'll probably end up there.

[3]	Chuck's handler... seriously.

Approach

For each number, check if it is prime. If so, then it is not a Carmichael number. Otherwise, perform the fermat test on all numbers from 2 to n - 1. If the tests succeed, then it is a Carmichael number. To handler large numbers use a divide and conquer method to compute the fermat test.

Input/Output

• Final Input: problem018.input
• Final Output: problem018.output

Source Code

• Peter Bui's source code: pbui.c
• Steve Lagree's source code: slagree.cpp