426,083 Members | 1,608 Online
Need help? Post your question and get tips & solutions from a community of 426,083 IT Pros & Developers. It's quick & easy.

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

 P: n/a 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) Feb 13 '08 #1
8 Replies

 P: n/a On Wed, 2008-02-13 at 10:40 -0800, me********@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 Feb 13 '08 #2

 P: n/a On Feb 13, 12:53*pm, Carsten Haese ## 5 None ## 6 <_sre.SRE_Match object at 0x011761A0> ## 7 None ## 8 <_sre.SRE_Match object at 0x011761A0> ## 9 <_sre.SRE_Match object at 0x011761A0> ## 10 <_sre.SRE_Match object at 0x011761A0> ## 11 None ## 12 <_sre.SRE_Match object at 0x011761A0> ## 13 None ## 14 <_sre.SRE_Match object at 0x011761A0> ## 15 <_sre.SRE_Match object at 0x011761A0> ## 16 <_sre.SRE_Match object at 0x011761A0> ## 17 None ## 18 <_sre.SRE_Match object at 0x011761A0> ## 19 None > -- Carsten Haesehttp://informixdb.sourceforge.net Feb 13 '08 #3

 P: n/a hmm... interesting here is another way you can find prime numbers http://love-python.blogspot.com/2008...ms-range2.html On Feb 13, 9:31 pm, cokofree...@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) Feb 13 '08 #4

 P: n/a On Feb 13, 5:14*pm, castiro...@gmail.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 Feb 13 '08 #5

 P: n/a On Feb 13, 5:43*pm, Mark Dickinson

 P: n/a 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... Feb 14 '08 #7

 P: n/a 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 Feb 14 '08 #8

 P: n/a 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 Feb 14 '08 #9

### This discussion thread is closed

Replies have been disabled for this discussion.