12

This is the function:

var isPrime = function(x) {
    return (!(/^,?$|^(,,+?)\1+$/.test(Array(++x))));
};

It works for small numbers, but when the number is large, throws an exception saying invalid array length. I cannot understand what's going on here. What does the RegEx test do? Why does this code work?

thefourtheye
  • 233,700
  • 52
  • 457
  • 497
Mr. X
  • 706
  • 12
  • 23
  • @dystroy This is not a challenge. I found this code somewhere and I want to understand what's going on inside it. – Mr. X Mar 21 '14 at 10:09
  • There is no way a regexp is going to check if a number is prime or not. Try this: http://en.wikipedia.org/wiki/Primality_test http://en.wikipedia.org/wiki/Wilson%27s_theorem – enriquinho Mar 21 '14 at 10:15
  • 3
    @epuigvros Believe it or not, it does ;) It works for atleast all the primes and non-primes I tried – thefourtheye Mar 21 '14 at 10:15
  • 2
    [*Related ...*](http://stackoverflow.com/q/2795065) – HamZa Mar 21 '14 at 10:18
  • @thefourtheye Well it doesn't work for x=1 – enriquinho Mar 21 '14 at 10:18
  • 1
    @epuigvros 1 is *not* a prime number – thefourtheye Mar 21 '14 at 10:19
  • 3
    @HamZa - I agree that the link you posted is a "near enough duplicate"; although the language is different, the mechanism is essentially the same. How on earth did you dig that up? – Floris Mar 21 '14 at 10:28
  • @epuigvros how are you links supposed to prove the test doesn't work ? – Denys Séguret Mar 21 '14 at 10:28
  • 2
    @Floris I was once searching for advanced regex tutorials/Q&A so I stumped on that question a while ago. – HamZa Mar 21 '14 at 10:29
  • 1
    @dystroy I was wrong, it does work, never thought a regexp could be used for this LMAO Anyway this approach is bad. – enriquinho Mar 21 '14 at 10:31
  • 1
    I have found a very old (2007) explanation of essentially the same expression [here](http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/). – Floris Mar 21 '14 at 10:33
  • Dup-voted, so that both the questions can be found together. – thefourtheye Mar 21 '14 at 10:34
  • 1
    @epuigvros "this approach is bad"? Other than "horribly inefficient and likely to crash with large numbers", what makes you say "bad"? That's such an undescriptive word... – Floris Mar 21 '14 at 10:34

2 Answers2

9

Array(++x) first produces a string of x commas.

The regex now:

^,?$         // Match 1 , or none
|            // or ...
^(,,+?)\1+$  // A specific number of commas, elaboration below:

The number of commas is equal to at least 2 commas, then repeat it till the end. What it's attempting to do is:

  • it first attempts to match 2 commas (,+? matches at least 1 , lazily), and use that to match all multiples of 2, except 2 itself because the backreference of \1 is compulsory. All multiples of 2 because ^(,,)\1+$ matches even number of ,.

    Sidenote: \1 is a backreference and will match what the first capture group matched, in this initial case (,,). So in this first phase, \1 will match 2 commas.

    If there's a match, it means that there are an even number of commas and that the number is not prime.

  • if the above didn't match, it then matches 3 commas, and use that to match all multiples of 3, again, except 3 itself. All multiples of 3 because ^(,,,)\1+$ matches numbers of , in multiples of 3.

    Sidenote: This time, \1 will match (,,,) since that's now in the capture group. So in this second phase, \1 will match 3 commas.

    If there's a match, it means that there are a number of commas that is divisible by 3, and hence, not a prime number.

And so on. You can see the pattern?

So the regex will actually check all numbers from 2 up until (,,+?) is equal in length to what Array(++x) returns. Of course, for big numbers, you can get different sorts of errors:

  1. The number you pass to the function is too large for the regex you'll get "a stack overflow as the regex is trying to keep too many things in memory as it's trying to find a match" as Floris mentioned in the comments (this occurs before the next error on node.js);

  2. The array formed by Array(++x) has too many elements which JS doesn't support.

So if the regex matches, it's not a prime number. That's also why you have ! at the start to negate the result of the regex test.

Jerry
  • 70,495
  • 13
  • 100
  • 144
  • 1
    Nice one Jerry. I had failed to notice that the last part actually checks for "any multiples". This explains why the expression crashes with large values - you get a stack overflow as the regex is trying to keep too many things in memory as it's trying to find a match... – Floris Mar 21 '14 at 10:23
  • 1
    Damn, why did the second answer be accepted ? – Denys Séguret Mar 21 '14 at 10:24
  • @Floris Thank you :) dystroy I... don't know :s – Jerry Mar 21 '14 at 10:24
7

Array(++x).toString() is a string of x commas.

This checks it's made of either :

  • ,? : zero or one comma
  • (,,+?)\1+ : a repetition of a number of commas at least 2

So it checks that x is either

  • 0 or 1
  • or a multiple of a number greater or equal to 2

That's the definition of what isn't a prime.

More detailed explanation :

  • /^A|B$ : A or B, from the start to the end
  • ,? : a comma, optional (so, 0 or 1
  • (,,+?) : 1 or more commas, but not greedy
  • \1+ the first group repeated one or more times

Note that there's no magic : it's expensive as it will ask the engine to test for all possible sizes of (,,+?) until it finds one.

Denys Séguret
  • 372,613
  • 87
  • 782
  • 758