A regular expression to check for prime numbers

Today i came across this article regarding regular expression to check for prime numbers.

It is really wonderful and i thank Avinash for putting in his blog.

Below code is used in java to achieve the same.

import java.util.regex.Pattern;

public class ArtlTest {
 
 public static void main(String[] args) {
  
  int!   c =7;

  String s = "";
  
  while (c > 0) {
   c--; 
   s+="1"; 
  }

  System.out.println(!Pattern.matches("^1?|^(11+?)\\1+", s));
 }
}

Few Notes:

if we keenly see what exactly this expression

(11+?)\\1+)

is doing

It matches with "1″ followed by one or more ones minimally. This means that it matches with "11″ initially.

The string obtained initially is bound to the variable

\\1

.

\1+ then matches with whatever has been matched above ("11″ initially) repeated one or more times! .


Let’s try to apply it to 9.

"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.

Cool isn't it?

Source: http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

prime expression