My prime Number generator

•

What is DaniWeb IT Discussion Community?

You're currently browsing the Python section within the Software Development category of DaniWeb, a massive community of 401,563 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 3,453 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Thread Tools Display Modes

Views: 7655 | Replies: 38

Page 4 of 4

« First

•

Join Date: Oct 2004

Location: Mojave Desert

Posts: 2,425

Reputation: vegaseat will become famous soon enough

Rep Power: 9

Solved Threads: 173

vegaseat

Offline

Kickbutt Moderator

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: 562

Reputation: jrcagle is on a distinguished road

Rep Power: 4

Solved Threads: 72

jrcagle

Offline

Posting Pro

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

Rep Power: 0

Solved Threads: 0

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

(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)

Again thanks for replies

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

•

Join Date: Oct 2004

Location: Mojave Desert

Posts: 2,425

Reputation: vegaseat will become famous soon enough

Rep Power: 9

Solved Threads: 173

vegaseat

Offline

Kickbutt Moderator

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

Rep Power: 0

Solved Threads: 0

arsham

Offline

Newbie Poster

Re: My prime Number generator

#35

Jun 3rd, 2007

Thanks
You are right
Must be :

Help with Code Tags

(Toggle Plain Text)

        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: 562

Reputation: jrcagle is on a distinguished road

Rep Power: 4

Solved Threads: 72

jrcagle

Offline

Posting Pro

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

Rep Power: 2

Solved Threads: 2

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 8:14 pm. Reason: updating my golfs

•

Join Date: May 2007

Posts: 15

Reputation: ffao is an unknown quantity at this point

Rep Power: 2

Solved Threads: 2

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 8:28 pm.

•

Join Date: Oct 2004

Location: Mojave Desert

Posts: 2,425

Reputation: vegaseat will become famous soon enough

Rep Power: 9

Solved Threads: 173

vegaseat

Offline

Kickbutt Moderator

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]
"""