DEV Community

João Paulo
João Paulo

Posted on

The interesting regex for Identifying Prime Numbers

Prime numbers are numbers greater than 1 that have no positive divisors other than 1 and themselves.

The regex is ^1?$|^(11+?)\1+$

Let's breaking Down...

First you need to know the meaning of these 3 symbols:

  • ^: start of the string
  • $: end of the string
  • |: OR operator

So we have two components in the main regex:

1?: The literal “1” and the question mark "?" for match the previous char zero or one times. So if we have zero characters or “1” it will match. Soon we will know the reason for this pattern here.

(11+?)\1+: The second pattern. (11+?) is a group and matches any string that starts with “11” by one or more “1”s. The “+?” makes it non-greedy, meaning it matches as few characters as possible.
\1+ capture the same text again with as many characters as possible.

E.g. So for the number '111111', the pattern '11' is repeated three times. For the number 5 ('11111'), there is no way to split it into repeated sub-patterns.

So the interesting thing is that we found how to evenly divide repeated sub patterns.
In the same number '111111', the pattern '111' is also repeated twice and this is captured by regex.
For prime numbers, the string cannot be divided evenly into repeating sub patterns.

Ah, and first pattern (1?) handles the non-prime cases of 0 and 1.

Thank you for reaching this point. If you need to contact me, here is my email: joaopauloj405@gmail.com

Sapere aude

Top comments (0)