Wyrażenie regularne, które potrafi sprawdzić, czy dana liczba jest pierwsza.

^1?$|^(11+?)\1+$

import static java.lang.System.*;

public class Prime {

	public static final String PRIME_REGEX = "^1?$|^(11+?)\\1+$";

	public static boolean isPrime(int i) {
		String s = "";
		while (i > 0) {
			i--;
			s += "1";
		}
		return !Pattern.matches(PRIME_REGEX, s); // escape the \1
	}

	public static void main(String[] args) {

		final int i = Integer.parseInt(args[0]);
		final boolean isPrime = isPrime(i);
		out.println(i + " is" + (isPrime ? "" : " not") + " a prime number");
	}
}

<barista@javaczyherbata.pl> java Prime 9
9 is not a prime number

Jak to działa?

Aby sprawdzić, czy dana liczba jest pierwsza, zapisuje się ją jako ciąg n jedynek, gdzie n równa się jej samej. Np. 5 reprezentowane jest przez ciąg „11111”.

Wyrażenie składa się z dwóch części oddzielonych „|” (or). Jeśli ciąg zostanie dopasowany, dana liczba nie jest pierwsza; w przeciwnym wypadku – jest.

Pierwsza część (^1?$) dopasowuje początek linii (^), zero lub jedną „1” (1?) oraz koniec linii.
Zatem dopasuje się do ciągów „” oraz „1” oznaczających kolejno cyfry 0 oraz 1. Jak wiemy 0 i 1 nie są liczbami pierwszymi.

Druga część wyrażenia (^(11+?)\1+$) jest bardziej skomplikowana. Dopasowuje początek linii (^), następnie jeden znak „1” oraz jeden lub więcej znaków „1” (11+?). To co zostało dopasowane, trafia w miejsce (\1) i jest dopasowywane jeden lub więcej razy (zachłannie). Następnie dopasowywany jest koniec linii. Ze względu na (zachłanny) znak „+” w \1+, jeśli nie powiedzie się dopasowanie z maksymalną ilością powtórzeń, nastąpi próba dopasowania z mniejszą ilością powtórzeń. Natomiast ze względu na (niezachłanny) znak „?” w 11+?, jeśli minimalny ciąg nie zostanie dopasowany, następuje próba dopasowania ciągu dłuższego o jeden znak.

Najlepiej obrazuje to przykład. Rozważmy cyfrę 9.

  1  1  1  1  1  1  1  1  1    ^(11+?) dopasowuje dwie jedynki "11" na początku 
^ (\1)                         i zapisuje je w \1

  1  1  1  1  1  1  1  1  1    następnie dopasowuje jeden lub więcej ciągów z \1,
^ (\1)  [  ]  [  ]  [  ]  $    ale dopasowanie się nie powodzi - to nie koniec ciągu

  1  1  1  1  1  1  1  1  1    dopasowanie mniejszej ilości powtórzeń \1 także się    
^ (\1)  [  ]  [  ]             nie powodzi

  1  1  1  1  1  1  1  1  1    dopasowanie jeszcze mniejszej ilości powtórzeń \1    
^ (\1)  [  ]                   także się nie powodzi

  1  1  1  1  1  1  1  1  1    ^(11+?) dopasowuje trzy jedynki "111" na początku
^ ( \1  )                      i zapisuje je w \1

  1  1  1  1  1  1  1  1  1        
^ ( \1  )  [     ]  [     ] $  dopasowuje kolejne dwa wystąpienia "111"; PASUJE

Zatem cyfra 9 nie jest liczbą pierwszą.