Yeah, it uses minimal matching and backreferences to test divide the number by everything from 2 to whenever the regex parser gives up (probably around n/2).
It was really confusing to me how this would work correctly on 12, 13, etc. until I read through there and realized that the program rewrote the number in unary (i.e. 2 -> 11, 3 -> 111, 4 -> 1111, etc.) before applying that regular expression.
From there, it does a quick test to correctly handle the zero and 1 case (empty string or a single 1), then it goes into the backtracking pattern, which tries to divide it by each number less than it until the parser succeeds or gives up. Anything matching is composite, anything not matching is prime.
Incidentally, whatever site he originally linked it from appears to be dead now.
It was really confusing to me how this would work correctly on 12, 13, etc. until I read through there and realized that the program rewrote the number in unary (i.e. 2 -> 11, 3 -> 111, 4 -> 1111, etc.) before applying that regular expression.
From there, it does a quick test to correctly handle the zero and 1 case (empty string or a single 1), then it goes into the backtracking pattern, which tries to divide it by each number less than it until the parser succeeds or gives up. Anything matching is composite, anything not matching is prime.
Incidentally, whatever site he originally linked it from appears to be dead now.