How to determine if a number is a prime with regex?

by

You said you understand this part, but just to emphasize, the String generated has a length equal to the number supplied. So the string has three characters if and only if n == 3.

.?

The first part of the regex says, “any character, zero or one times”. So basically, is there zero or one character– or, per what I mentioned above, n == 0 || n == 1. If we have the match, then return the negation of that. This corresponds with the fact that zero and one are NOT prime.

(..+?)\\1+

The second part of the regex is a little trickier, relying on groups and backreferences. A group is anything in parentheses, which will then be captured and stored by the regex engine for later use. A backreference is a matched group that is used later on in the same regex.

The group captures 1 character, then 1 or more of any character. (The + character means one or more, but ONLY of the previous character or group. So this is not “two or four or six etc. characters”, but rather “two or three etc.” The +? is like +, but it tries to match as few characters as possible. + normally tries to gobble the whole string if it can, which is bad in this case because it prevents the backreference part from working.)

The next part is the backreference: That same set of characters (two or more), appearing again. Said backreference appears one or more times.

So. The captured group corresponds to a natural number of characters (from 2 onward) captured. Said group then appears some natural number of times (also from 2 onward). If there IS a match, this implies that it’s possible to find a product of two numbers greater than or equal to 2 that match the n-length string… meaning you have a composite n. So again, return the negation of the successful match: n is NOT prime.

If no match can be found, then you can’t come up with a your product of two natural numbers greater than or equal to 2… and you have both a non-match and a prime, hence again the returning of the negation of the match result.

Do you see it now? It’s unbelievably tricky (and computationally expensive!) but it’s also kind of simple at the same time, once you get it. 🙂

I can elaborate if you have further questions, like on how regex parsing actually works. But I’m trying to keep this answer simple for now (or as simple as it can ever be).

More Related Contents:

  1. split US phone number in java? [closed]
  2. how to write regex for this expression in java
  3. Regular expression for SSN and phone number [closed]
  4. How do i find the first un-escaped quotes in Java?
  5. Incrementing only the digits from an alphanumeric string
  6. Prime number program does not work
  7. Specific String validation using regex
  8. Regexp Java for password validation
  9. Create array of regex matches
  10. Split string into array of character strings
  11. Regex Named Groups in Java
  12. List of all special characters that need to be escaped in a regex
  13. Regular expression to match URLs in Java
  14. Calculating and printing the nth prime number
  15. Detect and extract url from a string?
  16. What is the regex for “Any positive integer, excluding 0”
  17. Extract string between two strings in java
  18. Is Java Regex Thread Safe?
  19. How to extract parameters from a given url
  20. Passing parameters to action through ModelDriven in Struts 2
  21. How to use java regex to match a line
  22. Regex pattern including all special characters
  23. Java; String replace (school project)?
  24. Remove all non-“word characters” from a String in Java, leaving accented characters?
  25. java.util.regex.PatternSyntaxException: Dangling meta character ‘+’ near index 0 +
  26. How to escape a square bracket for Pattern compilation?
  27. String.replaceAll is considerably slower than doing the job yourself
  28. Remove all occurrences of \ from string
  29. Extract ip addresses from Strings using regex
  30. Validate if input string is a number between 0-255 using regex

Leave a Comment