in reply to Re: Prime Number Finder

in thread Prime Number Finder

Nice succinct algorithm, but I must take issue with

You do have to execute the algorithm on a classical computer, so Q::S or not, it's most definitelyThere's an interesting O(1) algorithm

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

blokhead

In Section
Snippets Section