Regular Expression for Prime Numbers (or How I came to fail at them, and love the bomb)

cokofreedom at cokofreedom at
Wed Feb 13 16:31:29 CET 2008

I was reading up on this site [
2007/03/18/a-regular-expression-to-check-for-prime-numbers/] of an
interesting way to work out prime numbers using Regular Expression.

However my attempts to use this in Python keep returning none
(obviously no match), however I don't see why, I was under the
impression Python used the same RE system as Perl/Ruby and I know the
convert is producing the correct display of 1's...Any thoughts?

def re_prime(n):
    import re
    convert = "".join("1" for i in xrange(n))
    return re.match("^1?$|^(11+?)\1+$", convert)

print re_prime(2)

Also on a side note the quickest method I have come across as yet is
the following

def prime_numbers(n):
    if n < 3: return [2] if n == 2 else []
    nroot = int(n ** 0.5) + 1
    sieve = range(n + 1)
    sieve[1] = 0
    for i in xrange(2, nroot):
        if sieve[i]:
            sieve[i * i: n + 1: i] = [0] * ((n / i - i) + 1)
    return [x for x in sieve if x]

Damn clever whoever built this (note sieve will produce a list the
size of your 'n' which is unfortunate)

More information about the Python-list mailing list