Posted By

banzaiman on 06/14/08


regex testing prime

Versions (?)

Who likes this?

3 people have marked this snippet as a favorite


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.

  1. ^1?$|^(11+?)\1+$

Report this snippet  


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:

You need to login to post a comment.