Challenge 21: Carmichael Numbers

Once again, agent Charles Carmichael ¹ has been captured by the rogue enemy spies. Fortunately, he has left clues about his location with the Nerd Herd at the Buy More ². 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 diligent 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 primality 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 ³ filter the list of numbers and determine which ones are Carmichael numbers.

Hint: Simply computing a^n mod n = a will lead to an overflow. Instead, you will need to manually perform modular exponentiation.

Input

The input will consist of a series of lines, each containing a small positive number n where (2 < n < 65,000). You should read until the end-of-file.

Example Input

1729
17
561
1109
431

Output

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

Example Output

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

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa17-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge21               # Create and checkout challenge21 branch

$ $EDITOR challenge21/program.cpp           # Edit your code

$ git add challenge21/program.cpp           # Stage your changes
$ git commit -m "challenge21: done"         # Commit your changes

$ git push -u origin challenge21            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge21 assignment ...
Submitting challenge21 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge21/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge21
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 11 TA List to determine your corresponding TA for the merge request.