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 ^{4}.
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-fa21-assignments # Go to assignments repository $ git checkout master # Make sure we are on master $ git pull --rebase # Pull any changes from GitHub $ git checkout -b challenge21 # Create and checkout challenge21 branch $ $EDITOR challenge21/program.py # Edit your code $ git add challenge21/program.py # Stage your changes $ git commit -m "challenge21: done" # Commit your changes $ git push -u origin challenge21 # Send changes to GitHub

To check your code, you can use the `.scripts/check.py`

script or curl:

$ .scripts/check.py Checking challenge21 program.py ... Result Success Time 0.06 Score 6.00 / 6.00 $ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge21 {"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}

Once you have committed your work and pushed it to GitHub, remember to
create a **pull request** and assign it to the appropriate **teaching
assistant** from the Reading 11 TA List.