Regular expressions are extremely powerful. This is something I read at least once or twice every day while reading articles and blogs on the Web.
While browsing today, I found this page which thoroughly describes the use of the regular expression /^1?$|^(11+?)\1+$/ in Perl to check if a number is prime or not!!!
To be frank, I was skeptical. The regular expression looks like magic! And I wanted to understand it better. I rewrote it in Ruby using irb and I tested it:
Avinash@noulakaz:~$ irb
irb(main):001:0> def is_prime(n)
irb(main):002:1> ("1" * n) !~ /^1?$|^(11+?)\1+$/
irb(main):003:1> end
=> nil
irb(main):004:0> is_prime(10)
=> false
irb(main):005:0> is_prime(11)
=> true
irb(main):006:0> is_prime(12)
=> false
irb(main):007:0> is_prime(13)
=> true
irb(main):008:0> is_prime(99)
=> false
irb(main):009:0> is_prime(100)
=> false
irb(main):010:0> is_prime(101)
=> true
Great! It also works in Ruby! This means that there is no (Perl) magic going on. The regular expression really works. But how? Let’s try to follow the logic behind it.
Is 7 prime?
To know this, the function first generates “1111111″ (from “1″ * 7) and tries to see if that string does not match /^1?$|^(11+?)\1+$/. If there is no match, then the number is prime.
Notice that the regular expression has two parts (separated with the vertical bar |).
The first part is /^1?$/ is trivial and matches with beginning of line (^), an optional 1 (1?)
and end of line ($) which implies that it matches either the empty string or “1″. This simply indicates that calling that function with n==0 or n==1 will correctly return false (as the “1″ * n will match with the first part of the regular expression)
The second part is where the magic occurs…
/^(11+?)\1+$/ matches with beginning of line (^) then by (11+?) then by \1+ and finally by end of line ($). I guess that you know that \1 is a variable which is bound to whatever was matched previously (in our case by (11+?)).
Let’s proceed slowly…
(11+?) does two things
- It matches with “1″ followed by one or more ones minimally. This means that it matches with “11″ initially (notice that if there was no ? (i.e. (11+) was used instead, the whole string would have matched)
- The string obtained (“11″ initially) is bound to the variable \1.
\1+ then matches with whatever has been matched above (“11″ initially) repeated one or more times. If this match succeeds then the number is not prime.
If you are following, you’ll realise that this eliminates all even numbers except 2 (for example, 8 is “11111111″ and therefore (11+?) will match with “11″ and \1+ will match with “111111″).
As for odd numbers (in our case 7), the (11+?) matches with “11″ initially but \1+$ cannot be true (notice the $) as there are 5 remaining ones. The regular expression engine will backtrack and will make (11+?) match “111″ and here also \1+$ won’t be true because there will be 4 remaining ones (and \1+$ will only match with a number of ones which is a multiple of 3 followed by end of line) etc. hence “1111111″ will not match the regular expression which implies that 7 will be considered as being prime 
When I showed this to Christina this morning (true), she told me that this only checked for a number being odd or not. This is also what I felt at the beginning. But it really works. For instance, let’s try to apply it to 9 (which is obviously not even), “1″ * 9 should match the regular expression…
“1″ * 9 = “111111111″. (11+?) matches “11″ initially. \1+$ cannot match because there are 7 remaining ones. Backtracking occurs. (11+?) now matches “111″. And here \1+$ matches the remaining 6 remaining ones! Hence, 9 is not prime.
Easy… and beautiful at the same time 
Popularity: 27% [?]
March 19th, 2007 at 18:23
unfortunately, I am quite allergic to regular expressions… too many bloody flavors to make any sense in the end.
March 19th, 2007 at 22:48
I fully understand. I was quite allergic to regexpr too. But little by little I have come to like and use them a lot.
Let’s see, I use regexpr when working with vi, grep, sed, awk and, now, ruby…
March 19th, 2007 at 23:51
I’ve been trying to write a bbcode parser for wordpress µ to cure it of kses.php while keeping the entries of the bloggers “safe”. So I have to figure out how to use regex.
So i guees i too will have to learn to like it.
It’s like voodoo.
March 20th, 2007 at 09:42
And I suppose you have realised that it is a small programming language… so it’s bound to be cool
March 21st, 2007 at 09:25
Programming Quiz No. 2
A serial file named contains a series of values, each of which is how many prime numbers ther are below a particular value. Write a program to read the number of primes between and values where and are requested interactively and compare it to the value obtained from FUNCT(limit) which is defined as limit / LOG(limit).
March 21st, 2007 at 13:34
Hi,
Seems that some of the text went missing… or you were seriously drunk
September 24th, 2007 at 23:19
Cool.. thx for your post. I like matematics quiz
September 25th, 2007 at 14:53
nice trick!
I find that the “backtracking” part was equivalence to finding out if the number is prime by brute-forcing
e.g. going from 3 to half the number and if any of that is divisible, its not a prime.
thus the ^(11+?)\1+& trick (anyone got it?)
i believe there are a lot of fast algorithms out there to use instead of generating 1s and parsing them with a regular expression which is kinda slow.
however this is truly magic ^^
September 29th, 2007 at 07:50
hey avinash, what is the exact input that goes to the regex constructor. I am not a ruby programmer but my attempt to use this regex in javascript failed. The test always failed for both prime and composite numbers. If you know javascript please help show me a sample to use this in javascript pls
October 3rd, 2007 at 17:53
the trick is to apply the regex to a string with n 1’s, for example, for 5, apply the regex to 11111.
October 7th, 2007 at 10:55
A PHP Version:
!preg_match(‘/^1?$|^(11+?)\1+$/x’, str_repeat(‘1′, $n))
Example:
<?php
$n = 1;
while ($n < 1000000) {
if (!preg_match(‘/^1?$|^(11+?)\1+$/x’, str_repeat(‘1′, $n))) {
echo “$n: Prime\n”;
}
$n++;
}
?>
October 16th, 2007 at 17:19
C# version:
static void Main(string[] args)
{
int c;
if (args.Length == 1 && int.TryParse(args[0], out c))
Console.WriteLine(!Regex.IsMatch(new String(‘1′, c), @”^1?$|^(11+?)\1+$”));
}
October 19th, 2007 at 04:17
Java Version, nice tip btw, guess I should learn more about regular expressions. Java requires that the \ be \’d out, otherwise it sees it as a smiley face character and problems happen
.
public static void main(string[] args){
if (args.length >= 1)
{
int c = Integer.parseInt(args[0]);
String s = “”;
while (c > 0) {c–; s+=”1″;}
System.out.println(!Pattern.matches(“^1?$|^(11+?)\\1+$”, s));
}}
October 19th, 2007 at 09:11
This is just awesome…
January 30th, 2008 at 02:35
Hello,
February 10th, 2008 at 16:19
To be honest – regular expressions are “overused”… And are NOT that good. For example in PHP using just common str_replace(); would be in many cases much faster then preg_replace();
Problem is that people tend to use a lot of “sophisticated” code where it’s not necessary, only because it looks more “professional”. My thought on this is “I don’t care what others think – I just need my code to be fast, clean and as simple as it is possible”.
February 11th, 2008 at 01:32
True.
Sometimes regular expressions are extremely cryptic (like the one above in fact
) but they are also interesting to understand because they are essentially small programs written in a domain specific language.
February 19th, 2008 at 04:33
The magic is in the backtrack…. if it can find a number a=(11+?) that multiplied N times gives our number, it’s obvious that our number can’t be prime (our number = a*N, i.e. not prime)
February 27th, 2008 at 13:55
[...] More details on Avinash Meetoo’s Blog. [...]
March 26th, 2008 at 02:19
How many numbers does this count up to? whats the largest prime that can be found in *real* time?
I’m interested so mail me please.
March 26th, 2008 at 23:24
Hi Roscoe,
I’ve not done any performance test but I guess that if you use a compiled language like C with a good Regex implementation, then, maybe, you can generate prime numbers real fast.
On the other hand, if you really want to generate primes then have a look at The Sieve of Eratosthene.
April 2nd, 2008 at 23:38
Avinash. Super, I’ve been looking around for a Regex similar to this for a while. I’ve modified it to suit.
April 3rd, 2008 at 19:32
Hi Paul,
Great to know that you find this regular expression useful. I’d like to point out that I’m not the original author though
April 27th, 2008 at 03:22
if primenumber mod 2 is 0 then
isprime = true
wouldnt that be easier and faster? ^^
April 27th, 2008 at 03:30
sorry, its getting late here heh
if primenumber mod 2 != 0 then
isprime = true
April 27th, 2008 at 07:20
Hi Rasmus,
A prime number is not simply odd. Check this.
June 30th, 2008 at 15:44
I have never been able to understand regular expressions, what is the logic behind them?
July 1st, 2008 at 06:54
Hi Celina,
Regular expressions are not trivial. But they are very powerful. If you want to know more about them, this is a good start.
A lot of people also recommend this book.
July 10th, 2008 at 03:56
While it’s neat, it’s not a great idea to use for big numbers since it uses O(N^2) time and O(N) memory where even a trivial solution uses O(sqrt(N)) time and O(1) memory.
July 10th, 2008 at 07:56
True
I wonder if someone has actually done some benchmarking with large numbers?
July 10th, 2008 at 17:53
This regular expression does not use O(1) and O(N^2), its actually exponential in the size of the input. If it unpacks the number 7 (32 bit) to 7 1’s, thats 7*(32). So a 32 bit number 2147483648 would take up half a gig of memory.
July 29th, 2008 at 21:06
Please follow the link below for fact about primes
http://kadiprimality.blogspot.com/
September 13th, 2008 at 05:50
[...] The script seems to be working, but is not very efficient. While writing this script I found a regular expression that does the same thing, only a couple of hundred times [...]
December 24th, 2008 at 21:03
[...] Quelle: A regular expression to check for prime numbersTags: merken [...]
January 9th, 2009 at 11:59
Pls give me regex to match filename that doesn’t start with a number and have html extension.
January 9th, 2009 at 16:05
Maybe something like “^[^0-9].*html$”
Notice that the two ^ have very different meanings. The first one is an anchor which represents the beginning of the line. The second one is the “inverse” operator i.e. [^0-9] matches with any character excepts a digit.
January 9th, 2009 at 17:02
You could also try this: “^\D\w+.html”
((^)Start of line – (\D)Not a digit – (\w+)several letters – (.html)end with .html)
Works with the .NET flavor of regex…
January 11th, 2009 at 03:01
[...] Avinash Meetoo: Blog » A regular expression to check for prime numbers (tags: regexp prime number) Dans la catégorie Del.icio.us « links for 2009-01-09 [...]
January 11th, 2009 at 18:21
[...] habe ich bei Noulakaz einen sehr verwirrenden Weg gefunden eine Zahl auf eine Primzahl hin zu prüfen. Also ob zum [...]
January 18th, 2009 at 21:42
[...] is_prime?(1000000000) [FATAL] failed to allocate memory $ p.s.: is_prime? method taken from http://www.noulakaz.net/weblog/2007/…prime-numbers/ — Posted via [...]
January 19th, 2009 at 10:57
[...] an nice explanation of how it works. [...]
January 31st, 2009 at 19:41
for calculations with big numbers, try F#
February 26th, 2009 at 19:08
[...] source. [...]
March 31st, 2009 at 21:35
try this: 999999 on the above php regexp it says prime….
it isn’t ….
April 1st, 2009 at 11:11
So it seems that there is a bug lurking somewhere…
April 12th, 2009 at 17:51
I don’t think this is formally a regular expression, because of “?” character. The processing of a real regular expression never requires backtracking (i.e. never requires reading the input multiple times) and hence they are very fast once you generate the deterministic finite automata (DFA) for the given regular expression.
Programming languages usually provide extensions to regular expressions (like ? in this case) for convenience to the programmer. There are only 3 operators in formal regular languages, which are star (“*”), union (“|”) and concatenation. All other operators used in a regular expressions must be representable by using these 3, for example you can represent 0+ as 00* and so on. The operator “?” used in the above expression is something totally different and which in fact violates the rule that machines that process a regular expression can do so with finite amount of memory. Hence this expression is actually not regular and the language generated by it is not a regular language, mathematically.
April 12th, 2009 at 20:35
Mathematically, you may be right (but I am not so sure.) But, from a programming point of view, regular expressions have always allowed backtracking…
July 10th, 2009 at 21:25
php may reject large numbers silently due to recursion depth limit (which I think is 32767 levels), that’s why 999999 fails.
July 12th, 2009 at 22:48
Thanks for pointing this out…
July 16th, 2009 at 23:25
WOW, pretty cool! I have to revisit regular expressions it seems.
August 10th, 2009 at 19:33
[...] just saw the most impressive, intelligent use of the regular expression backtracking engine and simply have to re-post it in order to give my own decryption of the infinitely simple [...]
August 27th, 2009 at 14:19
[...] Update (27th August 2009): Someone pointed me to an alternative explanation here. [...]
September 17th, 2009 at 05:23
a language such that a string is made of binary alphabet( of 0s and 1s) and the number of zeros in the string is a 3 digit prime number…….is this language regular…??
can u pls help me out in this ……its a ques appeared in GATE entrance
November 3rd, 2009 at 16:14
this was good shit. thanks!
November 18th, 2009 at 22:23
This is really intriguing, but I’m unclear about your explanation about how it works (it definitely works). For example, try the number 49 (not prime) – 1111111111111111111111111111111111111111111111111 – neither (11)+ matches nor (111)+ matches, so you would think the regex would classify 49 as prime (it does not). So how does it really work?
November 21st, 2009 at 16:01
[...] A regular expression to check for prime numbers [...]
February 4th, 2010 at 20:24
I would rather see pattern like this: “^\d*[13579]$” in my scripts.
It’s clear, easy and I think it’s also faster then the one described. If you want negative numbers it’s easy to change.
Anyway it’s nice work and idea!
David
February 4th, 2010 at 20:29
Oh, hell – my bloody English. Forgot my previous note
Shit