Why am I getting TLE in folllowing code?

miller-rabin
spoj

#1

I am trying to solve http://www.spoj.com/problems/PAGAIN/en/ and in the comments people have said they used Miller Rabin. So I studied it and implemented it. I am getting TLE. Am I supposed to use some different algorithm or I need some optimization tricks?

My code : http://ideone.com/Zs26PV

This is my first Miller Rabin implementation