Regex to check for prime numbers

[kirubakaran]

http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

[paulgb]

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.

[endtime → paulgb]

I was thinking the same thing. IIRC, the language of prime numbers isn't context-free, either.

Though to be fair, since the universe is finite, no existing computer is powerful enough to check if an arbitrarily large number is prime.

[paulgb]

Site seems slow, here's a cached copy:

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

[cema]

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).

[JulianMorrison]

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

Cute.

[gojomo]

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...

[davidw → gojomo]

Yeah, it's a pretty old trick. I recall someone showing it off on #perl in about 1997.

[berntb → davidw]

Search for "Prime" on this insanely fun page, to see where it came from:

http://www.cpan.org/misc/japh

(Hmm... I'll use that as a fortune file. Just need to remove extra '%', if fortune barfs on them. Ah, haven't had fortune in my login since the 90s.)

[davidw → berntb]

Abigail! Bingo, that's who I recall posting it.