A regular expression for finding prime numbers

Given that there’s so much mathematicians don’t know about prime numbers, you might be surprised to learn that there’s a very simple regular expression for detecting prime numbers:

/^1?$|^(11+?)\\1+$/

If you’ve got access to Perl on the command line, try it out with some of these (just replace [number] with any integer):

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\\1+$/' [number]

An explanation is here which I admit I did not quite follow. A commenter at Hacker News adds a bit more context:

However while cute, it is very slow. It tries every possible factorization as a pattern match. When it succeeds, on a string of length n that means that n times it tries to match a string of length n against a specific pattern. This is O(n^2). Try it on primes like 35509, 195341, 526049 and 1030793 and you can observe the slowdown.

• mathematics
• programming