Advertise here with Carbon Ads

This site is made possible by member support. โค๏ธ

Big thanks to Arcustech for hosting the site and offering amazing tech support.

When you buy through links on kottke.org, I may earn an affiliate commission. Thanks for supporting the site!

kottke.org. home of fine hypertext products since 1998.

๐Ÿ”  ๐Ÿ’€  ๐Ÿ“ธ  ๐Ÿ˜ญ  ๐Ÿ•ณ๏ธ  ๐Ÿค   ๐ŸŽฌ  ๐Ÿฅ”

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.