advanced code snippet search

Posted By

banzaiman on 06/14/08


Tagged

regex testing prime


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

deepsoul
Tyster
jholderman


Prime number tester

 / Published in: Regular Expression
 

By the legendary abigail. Fails to match if and only if it is matched against a prime number of 1's. That is, '11' fails, but '1111' does not.

I once heard him talk why this works, but I forgot most of it.

Expand | Embed | Plain Text 
  1. ^1?$|^(11+?)\1+$

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: fhewitt on April 29, 2009

This have nothing to see with a "prime number tester"... Fail with 2,3,5,7,9,13,17,19...

And in fact with mostly all number who contain just "1" (1111 is divisible by 11, 11111 is divisible by 41, and 111111 is divisible by 3)

Posted By: deepsoul on August 2, 2009

The test works on unary notation, not decimal. So 2 is written as "11", 3 as "111", 17 as "11111111111111111" and so on. The first branch of the regex matches the empty string (representing 0) and "1" (representing 1), marking them as non-primes. The second branch succeeds if and only if the unary number consists of two or more times two or more 1s, which means it is the product of these two numbers (both at least 2), so not a prime. To print a string of primes and see that this works:

perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;'

See also: http://www.catb.org/jargon/html/O/one-liner-wars.html

You need to login to post a comment.