Efficient way to find lowest divisor of an integer.

Question

I have followed the given way to find the lowest divisor of an integer,

Let us assume n is the given integer.

• Check n is divisible by 2,

• If yes then 2 will be the lowest divisor

• else Get the square root of n.

• Divide the value of n with (3 to < square root(n)) if any value divides the n in that particular range. Then that will be the the
  lowest divisor. If nothing divides, then n is a prime number.

Is there any other efficient mathematical way available to simplify this process.? Links regarding the efficient ways are welcome.

Answer 1

Premature optimization is the root of all evil.

For example, in nearly every situation where I had to write code to sort an array of numbers, bubble sort was by far the most efficient implementation... because the time my program would save using a 'more efficient' sort, even when added up over all the times my program would ever be run, would be several orders of magnitude less than the time I would waste coding up a more complicated sort.

If you truly are in a situation where the act of asking your question on MSE is not already many orders of magnitude slower than simply using the simple algorithm you described, then, most likely, you are going to want to use one of the standard integer factoring algorithms (e.g. "pollard rho") to factor your number.

That said, an extremely simple optimization to the program you suggested is to only test the odd divisors in the last step, since you already know $2$ isn't a divisor.