Anvit Garg - 1 year ago 43
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`

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)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download