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 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 ^{3} 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.

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*.

```
1729
17
561
1109
431
```

For each number in the input, print whether it is a Carmichael number or not as shown in the 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.
```

This is based on 10006 - Carmichael Numbers problem on the UVa Online Judge.

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

```
$ cd path/to/cse-30872-fa18-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
Time 0.41
$ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa18/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.