9 ms·

Demystifying the regular expression that checks if a number is prime (2016)

159 points by aquir 2y ago

aquir 2y ago
Also check the Matt Parker video for a more entertaining explanation: https://www.youtube.com/watch?v=5vbk0TwkokM https://www.youtube.com/watch?v=5vbk0TwkokM
- sbuttgereit 2y ago
  I appreciate that he picks a subject dealing with regexes for his Halloween video. I can think of few things more frightening or appropriate.
- wodenokoto 2y ago
  Maybe I wasn't paying close enough attention, but didn't he forget to mention that numbers must be displayed in unary form and just jumps right into checking "111", as if one hundred and eleven is prime, when he is actually checking if 3 is a prime.
  - david-gpu 2y ago
    Yeah, that is the very first thing he did when he showed his python code.
    - jhardy54 2y ago
      I don’t think he drew attention to it, because a few minutes later he highlights that it isn’t actually as simple as he first expressed, and shows the “1” * n.
  - Suppafly 2y ago
    He covered it, but I don't think he explained what was going on particularly well. I'm surprised by all of the people claiming it was a good explanation. I think if he had picked a few numbers and actually worked them through the algorithm completely it would have been much more of a useful explanation.
    - wvbdmp 2y ago
      I agree. I’m not familiar with Python and figured the '1'*n was just a quirk to convert the int to a string, not an integral part of the process. Kind of a weird way to repeat a string, tbh, but I guess the concision is appreciated in typical Python applications like computer linguistics or something.
- yen223 2y ago
  I wish someone explained regexes to me as concisely as Matt Parker did in that video, it would have saved me so much trouble.
deleted 2y ago
[deleted]
deleted 2y ago
[deleted]
IgorPartola 2y ago
So in summary there is no special thing here about this being a regex: the program described by it basically just brute force tries to divide the given number by every number smaller than it, it’s just written in a way that isn’t obvious to understand. 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.
- userbinator 2y ago
  ...and the divide is effectively implemented by "multiplication", i.e. repeating the same match group (via backreference). It's one of those things that looks impossible at first, but you instantly turn to "of course that's how it works!" once you understand. That said, I still think this article is on the verbose side. Also, strictly speaking, it's not a "regular expression" but a "regex", as backreferences make the language more powerful than regular. https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages https://en.wikipedia.org/wiki/Regular_expression#Patterns_fo...
  - Suppafly 2y ago
    >Also, strictly speaking, it's not a "regular expression" but a "regex" And regex is short for regular expression, so you've essentially said nothing.
    - shagie 2y ago
      https://web.archive.org/web/20100112232513/http://dev.perl.org/perl6/doc/design/apo/A05.html https://web.archive.org/web/20100112232513/http://dev.perl.o... AUTHOR Larry Wall <larry@wall.org> Maintainer: Larry Wall <larry@wall.org> Date: 4 Jun 2002 Last Modified: 18 May 2006 Number: 5 Version: 7 This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).
bawolff 2y ago
To save a click, the regex in question is: ^1?$|^(11+?)\1+$ (it checks if a unary number is not prime. 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)
- forinti 2y ago
  I had a hunch that maybe a lookahead might help a bit, but it turned out to be slower: /^(..+?)(?=\1+$)/ Edit: of course, silly me, +? is non-greedy.
isoprophlex 2y ago
The precondition that you need to first convert to a unary number makes this feel like it's almost cheating. The regex is not totally trivial, but it's not super sophisticated either: conceptually 'just' a Sieve of Eratosthenes.
- fanf2 2y ago
  It isn’t a sieve, it’s trial division. For example, a sieve skips powers of primes but this regex tests them all.
  - ykonstant 2y ago
    Correct, I would be much more impressed with a regex implementing the sieve of Eratosthenes. Not that this is not amusing!
    - thechao 2y ago
      Implementing the real Sieve is quite a challenge in any language: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
      - ykonstant 2y ago
        Quite; motivated by that paper I implemented a decent sieve of Eratosthenes with the standard wheel factorization in Lean 4: https://github.com/ykonstant1/esiv https://github.com/ykonstant1/esiv
  - isoprophlex 2y ago
    I stand corrected :)
    - fanf2 2y ago
      To be fair, you aren’t alone! Matt Parker also said it’s the Sieve of Eratosthenes in his latest video.
pxeger1 2y ago
I like this regex, which divides a number by sqrt(2): (?=(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| Source: https://codegolf.stackexchange.com/a/198428 https://codegolf.stackexchange.com/a/198428
- sph 2y ago
  Very nice! Almost as complex as the regex to parse HTML: https://stackoverflow.com/a/1732454 https://stackoverflow.com/a/1732454
  - Suppafly 2y ago
    Reminds me of work, a coworker was telling me that a new guy, who eventually quit, was really close to solving an issue with had with HTML in some fields where it doesn't belong, and then mentioned that the new guy was using regex to do it. I was like, I doubt he was actually close to solving the problem. That said, he likely would have solved our need because it really is just a subset of HTML used for stylizing text and not the full language, but it's a harder problem than people initially think.
    - sph 2y ago
      I figure he quit after the nightmares of backtracking regexes consuming the world started.
  - tiagod 2y ago
    From the replies :) > In CS theory, regular languages are a strict subset of context-free languages, but regular expression implementations in mainstream programming languages are more powerful. As noulakaz.net/weblog/2007/03/18/… describes, so-called "regular expressions" can check for prime numbers in unary, which is certainly something that a regular expression from CS theory can't accomplish. – Adam Mihalcin Commented Mar 19, 2012 at 23:50
devit 2y ago
That's not a regular expression and it's a ridiculously inefficient way to check for primality.
- imglorp 2y ago
  I think he meant to say smallest maybe? Ie its description is terse, not its runtime.
deleted 2y ago
[deleted]
LunicLynx 2y ago
The title should be: … the regex that checks if the length of a string with the same characters is a prime number.
astrodust 2y ago
Isn't this based on an expression from Abigail then at Perlmonks? https://www.masteringperl.org/2013/06/how-abigails-prime-number-checker-works/ https://www.masteringperl.org/2013/06/how-abigails-prime-num...
gusfoo 2y ago
perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' <number> 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-for-prime-numbers/ 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.

159 points by aquir 2y ago

Also check the Matt Parker video for a more entertaining explanation: https://www.youtube.com/watch?v=5vbk0TwkokM https://www.youtube.com/watch?v=5vbk0TwkokM

sbuttgereit 2y ago
I appreciate that he picks a subject dealing with regexes for his Halloween video. I can think of few things more frightening or appropriate.
wodenokoto 2y ago
Maybe I wasn't paying close enough attention, but didn't he forget to mention that numbers must be displayed in unary form and just jumps right into checking "111", as if one hundred and eleven is prime, when he is actually checking if 3 is a prime.
- david-gpu 2y ago
  Yeah, that is the very first thing he did when he showed his python code.
  - jhardy54 2y ago
    I don’t think he drew attention to it, because a few minutes later he highlights that it isn’t actually as simple as he first expressed, and shows the “1” * n.
- Suppafly 2y ago
  He covered it, but I don't think he explained what was going on particularly well. I'm surprised by all of the people claiming it was a good explanation. I think if he had picked a few numbers and actually worked them through the algorithm completely it would have been much more of a useful explanation.
  - wvbdmp 2y ago
    I agree. I’m not familiar with Python and figured the '1'*n was just a quirk to convert the int to a string, not an integral part of the process. Kind of a weird way to repeat a string, tbh, but I guess the concision is appreciated in typical Python applications like computer linguistics or something.
yen223 2y ago
I wish someone explained regexes to me as concisely as Matt Parker did in that video, it would have saved me so much trouble.

deleted 2y ago

[deleted]

deleted 2y ago

[deleted]

IgorPartola 2y ago

So in summary there is no special thing here about this being a regex: the program described by it basically just brute force tries to divide the given number by every number smaller than it, it’s just written in a way that isn’t obvious to understand. 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.

userbinator 2y ago
...and the divide is effectively implemented by "multiplication", i.e. repeating the same match group (via backreference). It's one of those things that looks impossible at first, but you instantly turn to "of course that's how it works!" once you understand. That said, I still think this article is on the verbose side. Also, strictly speaking, it's not a "regular expression" but a "regex", as backreferences make the language more powerful than regular. https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages https://en.wikipedia.org/wiki/Regular_expression#Patterns_fo...
- Suppafly 2y ago
  >Also, strictly speaking, it's not a "regular expression" but a "regex" And regex is short for regular expression, so you've essentially said nothing.
  - shagie 2y ago
    https://web.archive.org/web/20100112232513/http://dev.perl.org/perl6/doc/design/apo/A05.html https://web.archive.org/web/20100112232513/http://dev.perl.o... AUTHOR Larry Wall <larry@wall.org> Maintainer: Larry Wall <larry@wall.org> Date: 4 Jun 2002 Last Modified: 18 May 2006 Number: 5 Version: 7 This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).

bawolff 2y ago

To save a click, the regex in question is: ^1?$|^(11+?)\1+$ (it checks if a unary number is not prime. 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)

forinti 2y ago
I had a hunch that maybe a lookahead might help a bit, but it turned out to be slower: /^(..+?)(?=\1+$)/ Edit: of course, silly me, +? is non-greedy.

isoprophlex 2y ago

The precondition that you need to first convert to a unary number makes this feel like it's almost cheating. The regex is not totally trivial, but it's not super sophisticated either: conceptually 'just' a Sieve of Eratosthenes.

fanf2 2y ago
It isn’t a sieve, it’s trial division. For example, a sieve skips powers of primes but this regex tests them all.
- ykonstant 2y ago
  Correct, I would be much more impressed with a regex implementing the sieve of Eratosthenes. Not that this is not amusing!
  - thechao 2y ago
    Implementing the real Sieve is quite a challenge in any language: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
    - ykonstant 2y ago
      Quite; motivated by that paper I implemented a decent sieve of Eratosthenes with the standard wheel factorization in Lean 4: https://github.com/ykonstant1/esiv https://github.com/ykonstant1/esiv
- isoprophlex 2y ago
  I stand corrected :)
  - fanf2 2y ago
    To be fair, you aren’t alone! Matt Parker also said it’s the Sieve of Eratosthenes in his latest video.

pxeger1 2y ago

I like this regex, which divides a number by sqrt(2): (?=(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| Source: https://codegolf.stackexchange.com/a/198428 https://codegolf.stackexchange.com/a/198428

sph 2y ago
Very nice! Almost as complex as the regex to parse HTML: https://stackoverflow.com/a/1732454 https://stackoverflow.com/a/1732454
- Suppafly 2y ago
  Reminds me of work, a coworker was telling me that a new guy, who eventually quit, was really close to solving an issue with had with HTML in some fields where it doesn't belong, and then mentioned that the new guy was using regex to do it. I was like, I doubt he was actually close to solving the problem. That said, he likely would have solved our need because it really is just a subset of HTML used for stylizing text and not the full language, but it's a harder problem than people initially think.
  - sph 2y ago
    I figure he quit after the nightmares of backtracking regexes consuming the world started.
- tiagod 2y ago
  From the replies :) > In CS theory, regular languages are a strict subset of context-free languages, but regular expression implementations in mainstream programming languages are more powerful. As noulakaz.net/weblog/2007/03/18/… describes, so-called "regular expressions" can check for prime numbers in unary, which is certainly something that a regular expression from CS theory can't accomplish. – Adam Mihalcin Commented Mar 19, 2012 at 23:50

devit 2y ago

That's not a regular expression and it's a ridiculously inefficient way to check for primality.

imglorp 2y ago
I think he meant to say smallest maybe? Ie its description is terse, not its runtime.

deleted 2y ago

[deleted]

LunicLynx 2y ago

The title should be: … the regex that checks if the length of a string with the same characters is a prime number.

astrodust 2y ago

Isn't this based on an expression from Abigail then at Perlmonks? https://www.masteringperl.org/2013/06/how-abigails-prime-number-checker-works/ https://www.masteringperl.org/2013/06/how-abigails-prime-num...

gusfoo 2y ago

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' <number> 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-for-prime-numbers/ 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.