Anvit Garg Anvit Garg - 5 months ago 21
Python Question

Sieve of Eratosthenes leaving out some composites

Edit: OK, so the code is working now... Can anyone explain why changing

Floor(1000/index)
to
floor(999/index) + 1
helped?

My implementation of Sieve of Eratosthenes is listing some composites as primes in the end of list. That is, if I'm finding primes till 1000, some none primes between 980 and 1000 are also included

from math import floor

prime_list = []
list_primes2 = [True for x in range(1000)]
list_primes2[0], list_primes2[1] = False, False

for index, value in enumerate(list_primes2):
if value:
for x in range(floor(999/index)+1):
list_primes2[index*x] = False

prime_list.append(index)

print(prime_list)


the above code results in all primes upto 1000 plus 989 and 999

Prime Factors of 989 are 23 and 43 both of which are listed in
prime_list


Prime Factors of 999 are 3 and 37 both of which are listed in
prime_list

Answer Source

I tried messing with the 1000 figure to see if it would exhibit the same behaviour, as you were only seeing the errant output near the limit, and it appears that errant non-primes are kept in the list near the limit (wherever you set it, I tried up to 2000).

Short Answer: The problem appears to be that because of how your range(float(1000/index)) element is functioning, you're shaving off some values near the upper limit. It's not iterating through them, and is not taking them from your list of primes.

If you add 1 to that range it works, that is, it iterates through all the numbers it needs to, but you have to decrease 1000 to 999 to keep the product from rising to above 1000 (ie x in range(floor(1000/index)+1)). Otherwise that product is >999 and referring to a list index that is out of the original range you set: list_primes2 = [True for x in range(1000)]

Longer answer/how I got there: Your first range(1000) is 0, 1000. Your second is range(floor(1000/index))ie 0, 1 I believe it has to be thus because, as I understand it, floor() will give you the largest integer value less than or equal to x. For range(floor(1000/index)), the range will never be greater than one, because it went to float(1000/999) giving range 0, 1. Now if you use `range(floor((999/index)+1) you end with range 0, 2.

Now experimenting, it seems that if you do range(n), range(floor((n-1/index)+1) it works.

I printed out the x, index, product x*index range for every iteration: For the first set of parameters you used, it was only cycling through to x=23, index=42, so it was never returning 989, same for 999, it was never cycling through any combination of index and x that equalled 999. When you increase the range by one, it reaches all of those iterations. You have to decrease 1000 to 999 to keep the product from rising to above 1000 (ie x in range(floor(1000/index)+1)) and referring to a list index that is out of the original range you set: list_primes2 = [True for x in range(1000)]

from math import floor
prime_list = []
list_primes2 = [True for x in range(1000)]
list_primes2[0], list_primes2[1] = False, False
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(1000/index)):
            print (x)
            print (index)
            print (x*index)
            print (range(floor(1000/index)))
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(1000/index)):
            list_primes2[index*x] = False
        prime_list.append(index)
print(prime_list)


prime_list = []
list_primes2 = [True for x in range(1000)]
list_primes2[0], list_primes2[1] = False, False
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(999/index)+1):
            print (x)
            print (index)
            print (x*index)
            print(range(floor(999/index)+1))

for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(999/index)+1):
            list_primes2[index*x] = False
        prime_list.append(index)
print(prime_list)

Further: I think you may be misunderstanding how the Sieve is meant to work, or how the range is really working. With the sieve, you'll iterate over a number much fewer times, especially as you go upwards, that's part of it's usefulness: you mark off multiples of each prime going up, so you need to neither perform exhaustive tests on each number to find its compositeness or primeness. you just eliminate the multiples of each successive prime 2*(1...n), 3*(1...n), [4 is already elim], 5*(1...n) until you get to n.

We'll go to 20 so it's clearer. Only the multiples are "iterated over"

So  
x-[Eliminating]               [All Eliminated]                
2-[4,6,8,10,12,14,16,18,20]   [4,6,8,10,12,14,16,18,20]
3-[6,9,15]                    [4,6,8,9,10,12,14,15,16,18,20]
5-No more multiples <20       [4,5,6,8,9,10,12,14,15,16,18,20]          
7-No more multiples <20       [4,5,6,8,9,10,12,14,15,16,18,20]
11-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
13-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
17-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]
19-No more multiples <20      [4,5,6,8,9,10,12,14,15,16,18,20]

So We can see 0-10 is 4 steps, far less than your function runs.

We can test like in my previous answer, and it demonstrates this even if we set the limit as low as 10, there are 13 iterations - more than there are numbers.

from math import floor
prime_list = []
iterations=0
list_primes2 = [True for x in range(10)]
list_primes2[0], list_primes2[1] = False, False
for index, value in enumerate(list_primes2):
    if value:
        for x in range(floor(9/index)+1):
            iterations+=1
            print ("Iterations:",iterations)
            list_primes2[index*x] = False
            print ("X:         ",x)
            print ("index:     ",index)
            print ("x*index:   ",x*index)
            print(range(floor(9/index)+1))
            print("Numbers now in list of primes: ",prime_list)
            print()
        prime_list.append(index)

print("List of primes: ",prime_list)