# UVa 10006

Jump to navigation
Jump to search

## Contents

## 10006 - Carmichael Numbers[edit]

## Summary[edit]

Follow the instructions, and realize that you can compute in time, and without needing BigNum. The rest is simple.

## Explanation[edit]

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.

## Optimizations[edit]

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.

## Input[edit]

1729 17 561 1109 431 0

## Output[edit]

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

## Solutions[edit]

C++: http://codealltheproblems.blogspot.com/2015/06/uva-10006-carmichael-numbers.html