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

subeen tamim.shahriar at gmail.com
Wed Feb 13 20:36:00 CET 2008


hmm... interesting

here is another way you can find prime numbers
http://love-python.blogspot.com/2008/02/find-prime-number-upto-100-nums-range2.html



On Feb 13, 9:31 pm, cokofree... at gmail.com wrote:
> I was reading up on this site [http://www.noulakaz.net/weblog/
> 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