How does this weird JavaScript function for primality check work? [duplicate]

Question

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?

Answer 1

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.

Answer 2

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.