Python Boolean Array

[stalepretzel]

I'd like to make a prime sieve in python. It should be fairly large, from 0 to 10**8. The first step, was this:

Code: Select all

primes=[];
n = 0;
while n <= 10**8:
    primes.append(False);
    n+=1;

However, it took over 3 minutes just to complete that! Is there any way I can do this more efficiently?

Thanks,
Jason

[daniel.is.fischer]

I don't know if it's really more efficient, but try

Code: Select all

primes = [False]*10**8

Edit: Yep, definitely faster

[stalepretzel]

On a related note:
When, in Python, I use a for loop, it generates an entire array of numbers, which seriously clogs up my computer. For example:

Code: Select all

for n in range(1,10**8):
   print n;

This will cause my computer to freeze and, most likely, crash.
Is there any way around this, besides using a while loop?

[daniel.is.fischer]

Use xrange:

Code: Select all

for i in xrange(1,10**8):
    print i

Well, don't print 'em all

[3n1gm4]

Use xrange:

Code: Select all

for i in xrange(1,10**8):
    print i

Well, don't print 'em all

LOL!

Python is not for heavy math/cpu work. You should some external tool if you want to do it fast, try gmpy for example

[stalepretzel]

xrange. Well I feel sheepish. Baaa-a-a-a-a.

Thanks a bunch.

Wait... why, then, would anybody ever use range(a,b) instead of xrange(a,b)?

[quilan]

xrange. Well I feel sheepish. Baaa-a-a-a-a.

Thanks a bunch.

Wait... why, then, would anybody ever use range(a,b) instead of xrange(a,b)?

range() will be replaced by xrange() I believe in future versions.

[3n1gm4]

range() returns a list, xrange() returns an iterator.

You can "re-code" range and xrange in python like this:

Code: Select all

def xrange(start, stop, step = 1):
    while start<stop:
        yield start
        start += step

def range(stop, start = 0, step = 1):
    return [i for i in xrange(start,stop,step)]

xrange compute each iteration one by one (it yields it after it has calculated it), range compute all iterations then return the list. xrange will use less memory (ram) than range.
Testing it is very easy: run these codes:

Code: Select all

for i in xrange(0,100000000): print '.',
print 'Now with range...'
for i in range(100000000): print '.',

Now, you don't want python to print 100000000 '.'s ... so try them separately, you will see that the xrange version will start immediately to print out points, the range version will not, you'll see (i mean, wait for...) it loading all the 100000000 numbers in memory before to start looping :\


Anyway there are some interesting thing about this on stackoverflow.