4 ms·
Regex to check for prime numbers
- cema 17y agoBrute 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).
- gojomo 17y agoThis has been mentioned here before: http://news.ycombinator.com/item?id=230292 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/&syn=perlSyntax&anim=1&rep=&in=1111111111111111111111111111111111111111111111111 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/&syn=perlSyntax&anim=1&rep=&in=11111111111111111111111111111111111111111111111 http://regex.powertoy.org/?pat=/^1%3F%24|^%2811+%3F%29\1+%24...
- davidw 17y agoYeah, it's a pretty old trick. I recall someone showing it off on #perl in about 1997.
- berntb 17y agoSearch for "Prime" on this insanely fun page, to see where it came from: http://www.cpan.org/misc/japh 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 17y agoAbigail! Bingo, that's who I recall posting it.
- paulgb 17y agoSite seems slow, here's a cached copy: http://74.125.95.132/search?q=cache:d_FZMU2REmIJ:www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/+a-regular-expression-to-check-for-prime-numbers&hl=en&client=firefox-a&gl=us&strip=1 http://74.125.95.132/search?q=cache:d_FZMU2REmIJ:www.noulaka...
- paulgb 17y agoThis 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 17y agoI 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.
- JulianMorrison 17y agoA unary non-prime is empty, or 1, or composed of a series of at least two repetitions of at least two 1s. Cute.