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

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (0)

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay