CODEWITHSUNDEEP
javascriptregexprimes
Steve28
Steve28

Reputation: 39

How this prime test function works?

I saw this prime test code at another programming commnunity.

isPrime=n=>!/^.$|^(..+)\1+$/.test(Array(n+1));

I can understand RegExp thing, But I couldn't understand how this is work.

Why empty array is inside a RegExp test? and why it works???
I searched it but i couldn't find any informations... :(

Upvotes: 2

Views: 105

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370979

To start with, the regex is being tested against Array(n+1)). When .test is passed a non-string, it gets cast to a string.

String(Array(5)) results in ,,,, (4 commas). String(Array(3)) results in ,, (2 commas), and so on. (All elements of the array are joined by ,, resulting in length - 1 commas).

So, isPrime(n) results in a regex being tested against a string composed of n commas.

Now, for the interesting bit: the regex. The first part is ^.$, a trivial case of when the input is 1. This doesn't really matter, so feel free to ignore it.

The important part is ^(..+)\1+$:

  • ^ - Start of string
  • ( - Start of group
    • ..+ - Match 2 or more characters
  • ) - End of group
  • \1+ - Repeat the group that was previously matched 1 or more times
  • $ - End of string

In plain language, the initial capture group will match 2 or more characters, and then that capture group will be repeated 2 or more times total, and the full match will span the entire length of the string.

So, for example, the composite number 4 can be matched by ,, being matched in the first capture group, and by that group being backreferenced (matched again) once more.

The composite number 9 can be matched by ,,, being matched in the first capture group, and by that group being backreferenced twice more.

The prime number 5 cannot be matched, because there are no sub-segments of the string such that repeating the sub-segment N times (where N is 2 or more) will result in 5.

So, the whole regex /^.$|^(..+)\1+$/ will be fulfilled against a string if the string is composite. Invert that test, and you get a check of if the number of repeated commas is prime.

Upvotes: 6

Related Questions