Python

My prime Number generator

Please support our Python advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

« First

•

Join Date: Oct 2004

Posts: 4,113

Reputation: vegaseat is just really nice

Solved Threads: 944

vegaseat

Offline

DaniWeb's Hypocrite

Re: My prime Number generator

#31

Jun 1st, 2007

You need to test your code. This one does not work and contains nonprimes in the list!

May 'the Google' be with you!

•

Join Date: Jul 2006

Posts: 608

Reputation: jrcagle is on a distinguished road

Solved Threads: 150

jrcagle

Offline

Practically a Master Poster

Re: My prime Number generator

#32

Jun 1st, 2007

The second one is broken.

int(sqrt(len(myarray))) is not guaranteed to be the same as int(sqrt(i)), which is the last number that needs to be tested. Consider that for i = 49,

myarray == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
len(myarray) == 15
and int(sqrt(len(myarray))) == 3

Clearly, 3 is an inadequate bound, as 7 needs to be tested!!

Also, making slices as you go probably negates any speed-ups from using filter().

Jeff

•

Join Date: Jan 2007

Posts: 8

Reputation: arsham is an unknown quantity at this point

Solved Threads: 2

arsham

Offline

Newbie Poster

Re: My prime Number generator

#33

Jun 2nd, 2007

Thanks all for replies
I tested this one , no non-primes there , and x+1 is for the 49 problem :

 Help with Code Tags 
 Python Syntax (Toggle Plain Text) 
myarray = [2,3]
from math import sqrt
def prime(x):
    for i in xrange(3, x+1,2): 
        mylist = map(lambda x: i % x,myarray[0:int(sqrt(len(myarray)))])
        if 0 not in mylist:
            myarray.append(i)
myarray = [2,3]
from math import sqrt
def prime(x):
    for i in xrange(3, x+1,2): 
        mylist = map(lambda x: i % x,myarray[0:int(sqrt(len(myarray)))])
        if 0 not in mylist:
            myarray.append(i)

Again thanks for replies

Last edited by arsham; Jun 2nd, 2007 at 3:43 pm.

•

Join Date: Oct 2004

Posts: 4,113

Reputation: vegaseat is just really nice

Solved Threads: 944

vegaseat

Offline

DaniWeb's Hypocrite

Re: My prime Number generator

#34

Jun 3rd, 2007

Not quite there yet ...

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
myarray = [2, 3]
from math import sqrt
def prime(x):
    for i in xrange(3, x+1,2):
        mylist = map(lambda x: i % x,myarray[0:int(sqrt(len(myarray)))])
        if 0 not in mylist:
            myarray.append(i)
 
prime(50)
print myarray
"""
result -->
[2, 3, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
should be -->
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
"""
myarray = [2, 3]
from math import sqrt
def prime(x):
    for i in xrange(3, x+1,2):
        mylist = map(lambda x: i % x,myarray[0:int(sqrt(len(myarray)))])
        if 0 not in mylist:
            myarray.append(i)
 
prime(50)
print myarray
"""
result -->
[2, 3, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49]
should be -->
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
"""

May 'the Google' be with you!

•

Join Date: Jan 2007

Posts: 8

Reputation: arsham is an unknown quantity at this point

Solved Threads: 2

arsham

Offline

Newbie Poster

Re: My prime Number generator

#35

Jun 3rd, 2007

Thanks
You are right
Must be :

 Help with Code Tags 
 Python Syntax (Toggle Plain Text) 
        if 0 not in map(lambda x: i % x, myarray[0:int(sqrt(len(myarray)))+1]):
            myarray.append(i)
        if 0 not in map(lambda x: i % x, myarray[0:int(sqrt(len(myarray)))+1]):
            myarray.append(i)

a sqrt(x)+1 must be in test

Regards

•

Join Date: Jul 2006

Posts: 608

Reputation: jrcagle is on a distinguished road

Solved Threads: 150

jrcagle

Offline

Practically a Master Poster

Re: My prime Number generator

#36

Jun 5th, 2007

I'm confused about the math behind

myarray[0:int(sqrt(len(myarray)))+1]

It seems to me that this could not work in general, since the largest number to be tested has to be sqrt(n), and sqrt(len(primes(n)) < sqrt(n), since len(primes(n)) < n.

But I may be missing something subtle.

Jeff

•

Join Date: May 2007

Posts: 15

Reputation: ffao is an unknown quantity at this point

Solved Threads: 4

ffao

Offline

Newbie Poster

Re: My prime Number generator

#37

Jun 6th, 2007

•

Originally Posted by jrcagle

since the largest number to be tested has to be sqrt(n), and sqrt(len(primes(n)) < sqrt(n), since len(primes(n)) < n.

Note that it's not the sqrt(len(primes(n)) natural number, it's the sqrt(len(primes(n)) prime.

I'm curious as to how this works exactly, perhaps it's because the primes array grows faster than sqrt(n), I don't know.

EDIT: A basic debugging showed me some numbers were being tested by too many factors, which seems to corroborate with my theory (such as 99 being divided by 13).

As your intent seemed to be creating a golf, try to beat mine:

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
p = lambda x: [i for i in range(2,x+1) if all(map(lambda x: i % x,range(2,i**0.5+1)))]
p = lambda x: [i for i in range(2,x+1) if all(map(lambda x: i % x,range(2,i**0.5+1)))]

EDIT2: Removing extraneous spaces:
[code=python]
p = lambda x:[i for i in range(2,x+1) if all(map(lambda x:i%x,range(2,i**0.5+1)))]

Filter is actually one char bigger, because you need a lambda...

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
p = lambda x:filter(lambda i:all(map(lambda x:i%x,range(2,i**0.5+1))),range(2,x+1))
p = lambda x:filter(lambda i:all(map(lambda x:i%x,range(2,i**0.5+1))),range(2,x+1))

Last edited by ffao; Jun 6th, 2007 at 9:14 pm. Reason: updating my golfs

•

Join Date: May 2007

Posts: 15

Reputation: ffao is an unknown quantity at this point

Solved Threads: 4

ffao

Offline

Newbie Poster

Re: My prime Number generator

#38

Jun 6th, 2007

When I realized the filter was actually bigger, I transformed the map-loop into a comprehension as well:

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
p=lambda x:[i for i in range(2,x+1) if all([i%x for x in range(2,i**0.5+1)])]
p=lambda x:[i for i in range(2,x+1) if all([i%x for x in range(2,i**0.5+1)])]

Can anybody do better?

EDIT: 73 chars now:

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
p=lambda x:[i for i in range(2,x+1)if sum(i%d<1 for d in range(2,i+1))<2]
p=lambda x:[i for i in range(2,x+1)if sum(i%d<1 for d in range(2,i+1))<2]

Last edited by ffao; Jun 6th, 2007 at 9:28 pm.

•

Join Date: Oct 2004

Posts: 4,113

Reputation: vegaseat is just really nice

Solved Threads: 944

vegaseat

Offline

DaniWeb's Hypocrite

Re: My prime Number generator

#39

Jun 15th, 2007

Nice work ffao! Maybe you can post that in "Python Bitch", that would be a tough one to bitch about. I like the second code, since it also works with Python24.
From ffao ...

 Help with Code Tags 
 python Syntax (Toggle Plain Text) 
p=lambda x:[i for i in range(2,x+1)if sum(i%d<1 for d in range(2,i+1))<2]
 
print p(100)
 
"""
result -->
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
"""
p=lambda x:[i for i in range(2,x+1)if sum(i%d<1 for d in range(2,i+1))<2]
 
print p(100)
 
"""
result -->
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
"""