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

[cokofreedom@gmail.com]

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)

[Carsten Haese]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

On Wed, 2008-02-13 at 10:40 -0800, mensanator@aol. com wrote:

But why doesn't it work when you make that change?

I can't answer that question, because it *does* work when you make that
change.

--
Carsten Haese

http://informixdb.sourceforge.net

[mensanator@aol.com]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

On Feb 13, 12:53 pm, Carsten Haese <cars...@uniqsy s.comwrote:

On Wed, 2008-02-13 at 10:40 -0800, mensana...@aol. com wrote:

But why doesn't it work when you make that change?

>
I can't answer that question, because it *does* work when you make that
change.

Well, the OP said the function was returning None which meant
no match which implies None means composite for the given example 2.

If None was supposed to mean prime, then why would returing None
for 2 be a problem?

But isn't this kind of silly?

## 3 None
## 4 <_sre.SRE_Mat ch object at 0x011761A0>
## 5 None
## 6 <_sre.SRE_Mat ch object at 0x011761A0>
## 7 None
## 8 <_sre.SRE_Mat ch object at 0x011761A0>
## 9 <_sre.SRE_Mat ch object at 0x011761A0>
## 10 <_sre.SRE_Mat ch object at 0x011761A0>
## 11 None
## 12 <_sre.SRE_Mat ch object at 0x011761A0>
## 13 None
## 14 <_sre.SRE_Mat ch object at 0x011761A0>
## 15 <_sre.SRE_Mat ch object at 0x011761A0>
## 16 <_sre.SRE_Mat ch object at 0x011761A0>
## 17 None
## 18 <_sre.SRE_Mat ch object at 0x011761A0>
## 19 None

>
--
Carsten Haesehttp://informixdb.sour ceforge.net

[subeen]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

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...@gma il.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)

[Mark Dickinson]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

On Feb 13, 5:14 pm, castiro...@gmai l.com wrote:

Isn't the finite state machine "regular expression 'object'" really
large?

There's no finite state machine involved here, since this isn't a
regular expression in the strictest sense of the term---it doesn't
translate to a finite state machine, since backreferences are
involved.

Mark

[castironpi@gmail.com]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

On Feb 13, 5:43 pm, Mark Dickinson <dicki...@gmail .comwrote:

On Feb 13, 5:14 pm, castiro...@gmai l.com wrote:
>

Isn't the finite state machine "regular expression 'object'" really
large?

>
There's no finite state machine involved here, since this isn't a
regular expression in the strictest sense of the term---it doesn't
translate to a finite state machine, since backreferences are
involved.
>
Mark

What is it?

[cokofreedom@gmail.com]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

hmm... interesting

>
here is another way you can find prime numbershttp://love-python.blogspot .com/2008/02/find-prime-number-upto-100-nu...
>

Sadly that is pretty slow though...

If you don't mind readability you can make the example I gave into
five lines.

def p(_):
if _<3:return[2]if _==2 else[]
a,b,b[1]=int(_**0.5)+1, range(_+1),0
for c in xrange(2,a):
if b[c]:b[c*c:_+1:c]=[0]*((_/c-c)+1)
return[_ for _ in b if _]

But then, I would have to kill you...

[bearophileHUGS@lycos.com]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

cokofree:

Sadly that is pretty slow though...

It's quadratic, and it's not even short, you can do (quadratic still):

print [x for x in range(2, 100) if all(x%i for i in range(2, x))]

In D you can write similar code.
Bye,
bearophile

[castironpi@gmail.com]

Re: Regular Expression for Prime Numbers (or How I came to fail atthem, and love the bomb)

On Feb 14, 5:26 am, bearophileH...@ lycos.com wrote:

cokofree:
>

Sadly that is pretty slow though...

>
It's quadratic, and it's not even short, you can do (quadratic still):
>
print [x for x in range(2, 100) if all(x%i for i in range(2, x))]
>
In D you can write similar code.
Bye,
bearophile

all(x%i ha