Re code 1, I was solving for the largest divisor less than the square root so that was on purpose. Rereading the thread, we want instead <=. I've edited my answer to reflect this. Thanks for pointing that out.

While the results for the random numbers were identical, clearly they didn't include any perfect squares. I checked results from 2 to 100k and they now match the previous solutions (inlinec, pruner, rjnew, limbic). I started at 2 because some of those methods barf when given the input 1.

This wouldn't change the performance numbers. I did put in a different version of code 3 which may be faster, but I doubt it would change the timings by a lot.

Re divisors vs. factors, I think that is only true for very small inputs. That is, my thinking is that for factors we have lots of ways to speed things up -- e.g. trial division by only primes to square root of n, or better methods (e.g. Rho, P-1, SQUFOF, etc.). For divisors we need to do trial division by all numbers to square root of n and each found divisor isn't pruning the search space. The obvious optimization methods are limited forms of the "find factors, multiply out to get divisors" method.

To put this to the test, I used Math::Factor::XS. It has a function factors which loops from 2 to sqrt(n) adding the divisors to a list. It also has prime_factors which gives the prime factors using a mod-6 wheel trial division. I made two programs:

1. call factors and return the middle element.
2. call prime_factors, use my code 3 routine to calculate the divisors, return the middle element.

Is the first method faster? It's getting an array from an XS routine then returning one element from it. It should be fast. The second gets a smaller array from the XS routine then putzes around in Perl code making the divisor array. Yet the second method is faster once the inputs exceed about 400,000.

On the other hand, if the function that returns the divisors generates them via the factors (like the ntheory module does in both C and Perl, and Pari does in C), then we're probably better off just calling it. As the fastest solution on my list shows, as does the Pari divisors vs. various solutions using Pari factors. I could see some exceptions for special cases like primorials where some trimming solution could save some time (e.g. primorial(61) with 18 factors and 262,144 divisors)