Demystifying the regular expression that checks if a number is prime (2016)
The article presents a regex method in Java for determining prime numbers, explaining its components and providing examples across programming languages to aid understanding for readers of all skill levels.
Read original article
The article discusses a unique method for determining if a number is prime using a regular expression in Java. The code snippet provided utilizes the regex `!new String(new char[n]).matches(".?|(..+?)\\1+")`, which checks the unary representation of a number. The author explains that prime numbers are natural numbers greater than 1 that are only divisible by 1 and themselves. The regex works by matching patterns that indicate non-primality, specifically looking for repetitions of characters that would signify divisibility. The article aims to break down the regex components for readers of all skill levels, providing explanations of regex syntax, capturing groups, backreferences, and greedy versus non-greedy quantifiers. The author emphasizes the importance of understanding how the regex operates, particularly the two parts of the regex: `^.?$` (which matches 0 or 1 character) and `^(..+?)\1+$` (which matches multiples of 2). The explanation is intended to be accessible, even for those unfamiliar with regular expressions, and includes examples in various programming languages to illustrate the concept.
- The article explains a regex method for checking if a number is prime.
- It breaks down the regex components for clarity, targeting readers of all skill levels.
- Prime numbers are defined as natural numbers greater than 1 that are only divisible by 1 and themselves.
- The regex consists of two parts: one for matching 0 or 1 character and another for matching multiples of 2.
- The author provides examples in multiple programming languages to enhance understanding.
Related
Q Numbers
Tim Bray's ongoing fragment delves into Quamina's numeric representation and finite automata intersection. It addresses efficient event pattern matching, normalizing numbers for consistent comparison, and potential precision improvements. Introduced "Q numbers" aim for accurate matching despite performance considerations.
Crafting Formulas: Lambdas All the Way Down
The article details arbitrary-precision arithmetic in the Bruijn programming language, focusing on integers, rationals, and the challenges of real numbers, while discussing efficient representations and computational complexities.
Regex Crossword
A regex crossword puzzle challenges participants to fill a grid using simplified regex syntax. The author encourages learning regex basics and promotes their book on enhancing Python skills.
What is the longest known sequence that repeats in Pi? (homelab)
The article explores repeating sequences in Pi's decimal representation, detailing the transition from Python to C for efficiency, successful identification of sequences, and plans for further extensive searches.
Memorizing the first 100 perfect squares (2022)
The article outlines techniques for memorizing the first 100 perfect squares, emphasizing patterns and tricks over brute force memorization to aid mental calculations and recognize square numbers efficiently.
- Several commenters reference the historical context of the regex method, attributing it to Abigail's work in Perl.
- There is a debate about the efficiency and validity of using regex for primality testing, with some calling it inefficient and not truly a regular expression.
- Some users express skepticism about the method's sophistication, suggesting it is more of a brute-force approach rather than a clever mathematical trick.
- Others provide alternative regex examples and resources, highlighting the creativity involved in using regex for mathematical problems.
- Comments also discuss the specific regex pattern used, clarifying its function in determining whether a unary number is prime.
12 commentsThe regex is not totally trivial, but it's not super sophisticated either: conceptually 'just' a Sieve of Eratosthenes.
That’s not to detract from the excellent post, just that this isn’t a mathematical trick that exploits some structure of primes but rather an incredibly clever way to write a computer program.
(?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?*.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$)))(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$)\20|xx?\B|
It is kind of surprising to hear that regex can do that, but once you see the regex its kind of obvious. Its just checking if the number is 1, or if the number can be represented by 2 or more 1's repeated at least 2 times. Which is literally the definition of a prime (is the number divisible by a number >= 2)
I saw that by Abigail on comp.lang.perl.misc many moons ago. Here is an article about it: http://test.neilk.net/blog/2000/06/01/abigails-regex-to-test...
As far as I know, she was the genesis of this whole thing.
Related
Q Numbers
Tim Bray's ongoing fragment delves into Quamina's numeric representation and finite automata intersection. It addresses efficient event pattern matching, normalizing numbers for consistent comparison, and potential precision improvements. Introduced "Q numbers" aim for accurate matching despite performance considerations.
Crafting Formulas: Lambdas All the Way Down
The article details arbitrary-precision arithmetic in the Bruijn programming language, focusing on integers, rationals, and the challenges of real numbers, while discussing efficient representations and computational complexities.
Regex Crossword
A regex crossword puzzle challenges participants to fill a grid using simplified regex syntax. The author encourages learning regex basics and promotes their book on enhancing Python skills.
What is the longest known sequence that repeats in Pi? (homelab)
The article explores repeating sequences in Pi's decimal representation, detailing the transition from Python to C for efficiency, successful identification of sequences, and plans for further extensive searches.
Memorizing the first 100 perfect squares (2022)
The article outlines techniques for memorizing the first 100 perfect squares, emphasizing patterns and tricks over brute force memorization to aid mental calculations and recognize square numbers efficiently.