Nice succinct algorithm, but I must take issue with

*There's an interesting O(1) algorithm*

You do have to execute the algorithm on a classical computer, so Q::S or not, it's most definitely

*not* 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.

Just because it's a one-liner doesn't make it O(1). Anyway, my favorite cutesy inefficient primality checker is

`sub is_prime {
("1" x $_[0]) !~ /^(11+)\1+$/
}
`

Comment onRe^2: Prime Number FinderDownloadCode