0

So I am creating a list of primes using the "sieve" method and a Python comprehension.

no_primes = [j for i in range(2,sqrt_n) for j in range(i*2, n, i)]

Problem is the Sieve method generates tons of duplicates in the 'no_primes' list. It was recommended to use locals()['_[1]'] to gain access to the list as it is being built and then removing the dups as they occur:

no_primes = [j for i in range(2,sqrt_n) for j in range(i*2, n, i) if j not in locals()['_[1]']]

Problem is, this ability has been removed as of 2.7 and so does not work.

I understand that this method may be "evil" (Dr. Evil with his pinky at his lips.) , however, I need to remove dups before they affect memory with a massive list. Yes, I can filter or use 'set' to remove dups, but by then the list will have taken over my computer's memory and/or 'filter' or 'set' will have a massive task ahead.

So how do I get this ability back? I promise not to take over the world with it.

Thanks.

artem
  • 46,476
  • 8
  • 74
  • 78
Raw_Input
  • 341
  • 1
  • 5
  • 12

2 Answers2

3

You can use a set-comprehension (which automatically prevents duplicates):

no_primes = {j for i in range(2,sqrt_n) for j in range(i*2, n, i)}

You could then sort it into a list if necessary:

no_primes = sorted(no_primes)

For a further optimization, you can use xrange instead of range:

no_primes = {j for i in xrange(2,sqrt_n) for j in xrange(i*2, n, i)}

Unlike the latter, which produces an unnecessary list, xrange returns an iterator.

  • 1
    Should use xrange over range since this is 2.x and not 3.x – TM. Jul 13 '14 at 19:57
  • Fantastic! Works. I did not know about set-comprehension. I do now, and will research it further. Thanks. – Raw_Input Jul 13 '14 at 20:02
  • Just looked into the diffs in range() and xrange(). I never knew that range() created a list in memory and xrange() did not. Good info to know. Thanks. – Raw_Input Jul 15 '14 at 01:26
0

A simple and readable approach would be:

def get_primes(n):
    multiples = []
    for i in xrange(2, n+1):
        if i not in multiples:
            for j in xrange(i*i, n+1, i):
                multiples.append(j)
    return multiples

m = get_primes(100)
print m
user1636615
  • 102
  • 5