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.