Regex to check for prime numbers

This is clever and impressive.

For what it's worth, though, it is possible because most scripting languages make regular expressions more powerful by allowing you to match against previously captured values. As formally defined, regular expressions are not powerful enough to check whether an arbitrary number is prime.

Site seems slow, here's a cached copy:

http://74.125.95.132/search?q=cache:d_FZMU2REmIJ:www.noulaka...

Brute force but works. The real trick, for me at least, was to convert the number into a sequence of 1's. The rest was like an exercise in programming Turing machines (and a nice flashback into the freshman year of college).

A unary non-prime is empty, or 1, or composed of a series of at least two repetitions of at least two 1s.

Cute.

This has been mentioned here before:

http://news.ycombinator.com/item?id=230292

If your browser has Java applet support, here you can watch the regex succeed (demonstrating a number is composite) or fail (prime):

49: http://regex.powertoy.org/?pat=/^1%3F%24|^%2811+%3F%29\1+%24...

47: http://regex.powertoy.org/?pat=/^1%3F%24|^%2811+%3F%29\1+%24...