Wow, this is really amazing (to me at least because I had not seen or thought of this before).
[ Warning: Spoiler! :) ]
It's in base 1 (tally system).
The first part up to the "|" matches the case where number 1 is the whole string, covering the fact of 1 not being considered prime. It also matches no string, I guess to mean 0.
Next part matches a captured string consisting of 2 or more ones, and the captured string must be repeated at least one time. That is, 2+ repetitions of chunks of 2+ ones.
This much is obvious, but it wasn't until I wrote it out that I realized what it is doing:
multiples of 2
11+11 or 11+11+11 or 11+11+11+11 or ... = 4, 6, 8, 10, 12, ...
multiples of 3
111+111 or 111+111+111 or 111+111+111+111 or ... = 6, 9, 12, ...
multiples of 4
1111+1111 or 1111+1111+1111 or ... = 8, 12, 16, 20, ...
multiples of 5
11111+11111 or 11111+11111+11111 or ... = 10, 15, 20, 25, ...
[ Warning: Spoiler! :) ]
It's in base 1 (tally system).
The first part up to the "|" matches the case where number 1 is the whole string, covering the fact of 1 not being considered prime. It also matches no string, I guess to mean 0.
Next part matches a captured string consisting of 2 or more ones, and the captured string must be repeated at least one time. That is, 2+ repetitions of chunks of 2+ ones.
This much is obvious, but it wasn't until I wrote it out that I realized what it is doing:
multiples of 2
11+11 or 11+11+11 or 11+11+11+11 or ... = 4, 6, 8, 10, 12, ...
multiples of 3
111+111 or 111+111+111 or 111+111+111+111 or ... = 6, 9, 12, ...
multiples of 4
1111+1111 or 1111+1111+1111 or ... = 8, 12, 16, 20, ...
multiples of 5
11111+11111 or 11111+11111+11111 or ... = 10, 15, 20, 25, ...
multiples of n
which leaves only primes remaining.
Side note: In Perl, executing it this way:
$nstr = 1 x $ARGV[0]; print ($nstr =~ m/^1?$|^(11+?)\1+$/ ? "composite\n" : "prime\n");
The largest prime I can find without a seg fault is 37397
And the largest composite I can find without a seg fault is 37399