Technical Article => Programming => Perl

A Perl Regular Expression That Matches Prime Numbers

Can you figure out how it works? I give an explanation below, but try to figure it out yourself. Here is what happens when you run it:

$ perl -lne '(1x$_) =~ /^1?$|^(11+?)\1+$/ || print "$_ is prime"' 1 2 2 is prime 3 3 is prime 4 5 5 is prime 6 7 7 is prime 8 9 10 11 11 is prime

Here is how it works.

First, the number is converted in its unary representation by `(1x$_)`

. For example, the number `5`

gets converted into `1x5`

, which is `11111`

(`1`

repeated `5`

times.)

Next, the unary string gets tested against the regular expression. If it matches, the number is a composite, otherwise it's a prime.

The regular expression works this way. It consists of two parts `^1?$`

and `^(11+?)\1+$`

.

The first part matches number `1`

and the empty string. Clearly, the empty string and number `1`

are not prime numbers, therefore this regular expression matches, which indicates that they are not prime numbers.

The second part determines if two or more `1`

s repeatedly make up the whole number. If two or more `1`

s repeatedly make up the whole number, the regex matches, which means that the number is composite. Otherwise it's a prime.

Let's look at the second regex part on numbers `5`

and `4`

.

The number `5`

in unary representation is `11111`

. The `(11+?)`

matches the first two ones `11`

. The back-reference `\1`

becomes `11`

and the whole regex now becomes `^11(11)+$`

. It can't match five ones, therefore it fails. But since it used `+?`

, it backtracks and matches the first three ones `111`

. The back-reference becomes `111`

and the whole regex becomes `^111(111)+$`

. It doesn't match again. This repeats for `1111`

and `11111`

, which also don't match, therefore the whole regex doesn't match and the number is a prime.

The number `4`

in unary representation is `1111`

. The `(11+?)`

matches the first two ones `11`

. The back-reference `\1`

becomes `11`

and the regex becomes `^11(11)+$`

. It matches the original string, therefore the number is not a prime.

PS. I didn't invent this regular expression, it was invented in 1998 by Abigail.

Don't take this regular expression too seriously, it's actually neither a regular expression (as defined in automata theory), nor a way to check if a number is a prime. It's just an awesome thing that Perl can do.

Also if you wish to learn more about Perl one-liners, check out my Perl One-Liners Explained article series and download the perl1line.txt file.

Source : http://www.catonmat.net/blog/perl-regex-that-matches-prime-numbers/

#### RELATED

#### 0 COMMENT

No comment for this article.

## Apple Pencil? No. IKEA Pencil! |

By sonic0002 |

While the whole world raves about the recent Apple products and of course the advancements in the digital world, IKEA Singapore shows how traditional pen and paper still hold on to an old world charm. On its Facebook page, IKEA Singapore put up this post:
Obviously this is a post laughes at the Appl |