Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem which runs in $O(\log n)$ time and then check whether the number is prime or not by checking for existence of its divisors from $2$ to $\sqrt n$. But this will take $O(\sqrt n)$ time which is way beyond the machine's capability.

So how do I make Fermat's Little Theorem ultimate i.e. what are the values I'll need to run FLT with to ensure that it is prime or composite without having to go through $O(\sqrt n)$ operations?

share|cite|improve this question
Are you supposed to use Fermat's Little Theorem? – Mohammad Ali Baydoun May 8 '13 at 16:16
Yes.A O(log n) algorithm is the only feasible algorithm. In fermat's little theorem, I select a value a(<=(n-1)) and find a^(p-1) mod p. What I want is the values of a such that I am sure that the number is prime. Or any other possible solution is also acceptable. – sudeepdino008 May 8 '13 at 16:19
Why do you assume that $O(10^9)$ is 'way beyond the machine's capacity', what sort of machine is this? My machine executes $O(10^9)$ operations on a regular basis and I've run searches that did a couple of orders of magnitude more than that more than once... – Steven Stadnicki May 8 '13 at 16:21
What programming language do you use exactly? – Mohammad Ali Baydoun May 8 '13 at 16:23
There are no such values: – Micah May 8 '13 at 16:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.