Using the regular expression backtracking engine for prime number magic
July 16th, 2009 — 4:13pm
I just saw the most impressive, intelligent use of the regular expression backtracking engine and simply have to re-post it in order to give my own decryption of the infinitely simple expression. In short, it is a regular expression, that only matches non-prime sequences of 1’s. And it goes like this:
/^1?$|^(11+?)\1+$/
I will try to explain it in a simple way and then do some benchmarking on this simple expression, a slightly optimized version of the expression as well as compare it to more optimal algorithms.