homeaboutarchives + tagsshopmembership!
aboutarchivesshopmembership!
aboutarchivesmembers!

A regular expression for finding prime numbers

posted by Jason Kottke   Feb 12, 2015

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.