in reply to Re: Prime Number Finder
in thread Prime Number Finder

Even if you had a quantum computer to run it on, I'm not convinced you'd have an O(1) algorithm unless you also have O(1) algorithms for computing sqrt($n) and 2..$n.

In any case however the algorithm will give the wrong answer for 2. You can fix that by replacing sqrt($n)+1 with sqrt($n+1).