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.
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.
Programming Challanges
This is based on 10006 - Carmichael Numbers problem on the UVa Online Judge.
Submission
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.
Chuck Bartowski. ↩
If teaching this class doesn't work out, I'll probably end up there. ↩
Chuck's handler. ↩
