note
blokhead
Nice succinct algorithm, but I must take issue with
<blockquote><i>There's an interesting O(1) algorithm</i></blockquote>
You do have to execute the algorithm on a classical computer, so Q::S or not, it's most definitely <i>not</i> O(1). It'll be exponential (in the number of bits in $n) because behind the scenes, Q::S is dividing $n by all possible factors (what else could it be doing?). But even on a quantum computer, you still need either a division or gcd circuit (and probably a lot of other stuff), which will take some polynomial time in the number of bits.
<p>
Just because it's a one-liner doesn't make it O(1). Anyway, my favorite cutesy inefficient primality checker is
<code>
sub is_prime {
("1" x $_[0]) !~ /^(11+)\1+$/
}
</code>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-137386">
<p>
blokhead
</div></div>
143755
507703