10006 - Carmichael Numbers
Follow the instructions, and realize that you can compute in time, and without needing BigNum. The rest is simple.
The key is realizing that you can compute in time, and without needing BigNum. This means for a given , the total complexity is . (Note that the actual complexity relative to the input size is ) For small 's, this is good enough.
Note that there are only 15 Carmichael numbers within the range given, so you can actually precalculate them and check them with a simple statement.
1729 17 561 1109 431 0
The number 1729 is a Carmichael number. 17 is normal. The number 561 is a Carmichael number. 1109 is normal. 431 is normal.