4 ms·
How on Earth does ^.?$|^(..+?)\1+$ produce primes? [video]
- timonoko 2y agoRegexpr is confused with "+?" so ^.?$|^(..*)\1+$ is better.
- jfengel 2y agoThe answer is "by brutest possible force". It does trial division on the number in base 1 representation. That is, as a string of N 1s. It takes every sub-string of the number (except 0 and 1) and sees if you can reproduce the original in an integer number of steps. ^(..+?) is a substring of at least 2 characters at the beginning \1 is a copy of it +$ is the part doing the work: look for an exact number of copies, filling up the entire string The ^.?$ part is "0 and 1 don't count". It's basically equivalent to a for loop from 1 to N. Divide N by the number and look for a remainder. Except that the division is done in base 1, by duplicating the string over and over and seeing it it lines up. Clever, but certainly not useful.