My prime Number generator - Page 2

[vegaseat]

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

[jrcagle]

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

[arsham]

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

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

[vegaseat]

Not quite there yet ...

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

[arsham]

Thanks
You are right
Must be :

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

[jrcagle]

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

[ffao]

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:

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:

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...

[code=python]
p = lambda x:filter(lambda i:all(map(lambda x:i%x,range(2,i**0.5+1))),range(2,x+1))

[ffao]

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

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:

p=lambda x:[i for i in range(2,x+1)if sum(i%d<1 for d in range(2,i+1))<2]

[vegaseat]

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 ...

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