note
hv
<p>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 <c>sqrt($n)</c> and <c>2..$n</c>.</p>
<p>In any case however the algorithm will give the wrong answer for 2. You can fix that by replacing <c>sqrt($n)+1</c> with <c>sqrt($n+1)</c>.</p>
<p>Hugo</p>
143755
507703