Error in implementing Sieve of Eratosthenes

Question

I am getting an error in implementing 'Sieve of Eratosthenes' to get all the prime numbers between a specified range. I know my code is does not yet have primality checks, I will add them once I resolve the error.

def foo(l,r):
    if l == r:
        return "Error"
    if l > r:
        return "Error"
    if l < r:
        pool = set(xrange(l,r + 1))
        prime = 2
        if l == 1:
            print "Discard 1 for now"
        while prime <= r:
            rem = set(xrange(prime,r + 1,prime))
            pool.difference_update(rem)
            a = 0

            while prime >= pool[a]:
                a = a + 1
            prime = pool[a]
        print pool

foo(1,31623)

ERROR:

Traceback (most recent call last):
  File "D:\code\sieve_of_eratothenes.py", line 32, in <module>
    foo(1,31623)
  File "D:\code\sieve_of_eratothenes.py", line 27, in foo
    while prime >= pool[a]:
TypeError: 'set' object does not support indexing

For an example of using `set` to do a sieve: http://stackoverflow.com/a/9302299/5987 — Mark Ransom, Jun 28 '12 at 04:22

score 2 · Answer 1 · answered Jun 28 '12 at 04:21

2

The error is just what it says: sets don't support the retrieval of individual items via indexing. It looks like you want to use a list or xrange object instead (e.g., pool = xrange(l, r+1). Why did you use a set?

Note that the elements in the set are unordered, so iterating over them the way you're trying to do won't work. You can't assume the bigger primes will be at the "end" of the set.

answered Jun 28 '12 at 04:21

BrenBarn

242,874
37
412
384

I used the set so that I can directly difference out the multiples of the prime from pool of numbers. – Priyank Kapadia Jun 28 '12 at 04:23

score 2 · Accepted Answer · answered Jun 28 '12 at 04:34

2

You cannot reference a set element by index, however a set is iterable, so this:

a = 0
while prime >= pool[a]:
   a = a + 1
   prime = pool[a]

can be rewritten as:

for el in pool:
   if prime >= el:
       prime = el
       break

answered Jun 28 '12 at 04:34

Hamish

22,860
8
53
67

+1. And if you need the index for some reason, you can do "for a, el in enumerate(pool)". But it's worth pointing out that, although this solves his error, it doesn't make his algorithm work. As BrenBam pointed out, the elements of a set are unordered, but the OP seems to think he'll get the smallest primes first. – abarnert Jun 28 '12 at 04:36

Error in implementing Sieve of Eratosthenes

2 Answers2