It has been posted before [2], so I'll repost my comment from back then [3]: It's cool, but it's regexp, not regular expression -- regular expressions cannot t

It has been posted before [2], so I'll repost my comment from back then [3]: It's cool, but it's regexp, not regular expression -- regular expressions cannot test for primeness. The proof is a simple application of pumping lemma[1]: we want to show that language { a^p: p prime } is not regular. Suppose it is. By pumping lemma we have numbers N, n >= 1, such that for every k >= 0, we have a^(N+nk) in our language. But that means that for every k, N+nk is prime, and it fails for k = N, since N+nN = N(1+n) is not a prime, since both N and 1+n are greater than 1. [1] - http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu... [2] - https://news.ycombinator.com/item?id=3391547 https://news.ycombinator.com/item?id=3391547 [3] - https://news.ycombinator.com/item?id=3391572 https://news.ycombinator.com/item?id=3391572