A wonderful abuse of regular expressions

As it turns out, you can use regular expressions to test primality.

You'll need a regular expression engine that supports backreferences to do this. (Intuitively, a more restricted matcher that can be implemented as a finite state machine cannot count up to arbitrarily large numbers.)

I tried this in GNU egrep. I made this input file, which contains a number on each line followed by that number of stars:

$ cat numbers.txt
 2 **
 3 ***
 4 ****
 5 *****
 6 ******
 7 *******
 8 ********
 9 *********
10 **********
11 ***********
12 ************
13 *************
14 **************
15 ***************
16 ****************
17 *****************
18 ******************
19 *******************
20 ********************

Then, to find only those lines corresponding to prime numbers:

$ egrep -v " (\*{2,})\1+$" numbers.txt
 2 **
 3 ***
 5 *****
 7 *******
11 ***********
13 *************
17 *****************
19 *******************

Intuitively, the regular expression identifies composite numbers by seeing whether they can be written as a group of two or more stars, followed by one or more repetitions of that group. Writing the line in such a way corresponds of finding a factorization of the corresponding number into two other integers, both of which are greater than 1. The implementation basically carries out trial division by letting the first group be equal to **, then to ***, ****, etc. The -v option to egrep only prints those lines which do not match the regular expression, that is, the prime numbers.

Here's the catch:

Back-references are very slow, and may require exponential time.

(man page for GNU egrep)

Comparison of regexp syntax

To help myself learn Emacs regular expressions, I've put together this cheat sheet comparing regular expression syntax in Emacs, Python, and egrep.

Note that in Emacs, the syntax described below is for regular expressions that are entered directly (e.g. in isearch-forward-regexp and occur). When you provide a regexp in a string (e.g. in Lisp code or in re-builder) you need to double all backslashes.

	Emacs	Python	egrep
Any character	.	.	.
Beginning of line	^	^	^
End of line	$	$	$
0 or more repetitions	*	*	*
1 or more repetitions	+	+	+
3-5 repetitions	\{3,5\}	{3,5}	{3,5}
Optional	?	?	?
Character set	[...]	[...]	[...]
Alternatives	\|	|	|
Group	\(...\)	(...)	(...)
Named group		(?P<name>...)
Non-capturing group1	\(?:...\)	(?:...)
Word boundary	\b	\b	\b
Digit	[[:digit:]]	\d	[[:digit:]]
Whitespace char	\s-	\s
Alphanumeric char	\w	\w	\w
Back reference	\1		\1
Named back reference		(?P=name)

¹ Also referred to as "shy groups".