4 ms·
I guess you mean "For real?" as in "Is this really a primality test?" Yes, it is, and Krumins describes how it works in the post that I linked (http://www.cato
by JadeNB 10y ago
I guess you mean "For real?" as in "Is this really a primality test?" Yes, it is, and Krumins describes how it works in the post that I linked (http://www.catonmat.net/blog/perl-regex-that-matches-prime-numbers http://www.catonmat.net/blog/perl-regex-that-matches-prime-n...).
Essentially, although it looks complicated, it's the simplest possible idea: it's just trying factorisations, with the `(11+?)` part being the factor, and the `\1+` part insisting that we repeat that factor. It is of course wildly inefficient, and limitations in the backtracking engine mean that it can give false positives for large numbers (http://zmievski.org/2010/08/the-prime-that-wasnt http://zmievski.org/2010/08/the-prime-that-wasnt, also linked from that post).