You may get TLE if you are calculating carmichael number function again and again for each input. You should use such function just once, generating all carmichael numbers before reading any input. This may look like pre-calculating, but it is notb3yours3lf wrote:but i've test in my comp (Celeron 1,1 GHZ), it's only take 2 second to find all carmichael number < 65000, but when i submitted itu (only the function to find carmichael number) i got TLE.

Else, I read you may have problems if you use signed int (4 bytes), because 32 bits are needed to avoid overflow when calculating 65000 * 65000, so you need unsigned long (4 bytes, 32 bits) or long long (8 bytes, 63 bits + 1 bit for signal) types.

Hope I have helped, but now I need your help

How did you make such function? I failed to do it. Reading about carmichael numbers in mathworld didn't help either:

http://mathworld.wolfram.com/CarmichaelNumber.html

In my first attempt, I first tested if it is prime. If it is not, I test for all number 2<a<n if the equation "a^n mod n = a" is satisfied, but this would obviously cause overflow.

Please explain to me how to test if a number is Carmichael. You may send you function to murilop@email.iis.com.br