Re^2: Prime Number Finder

[blokhead]

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+$/
}