Question

Here is the algorithm:

1. Assume that all numbers are prime from 2..n, so put them in the list (2 is the smallest number, so if n is less than 2, the list should be empty).

2. Make the first item be current.

3. Leave in the current item. Then, take out all of its multiples (since any multiple will have that number as a factor).

4. Make current be the next element in primes.

5. If there are no more elements in the list, primes is the list of prime numbers from 2..n. Otherwise, go to Step 3

For example, sieve(20) would find the primes from 1 to 20. Step 1 assign primes to be [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] Step 2 assigns 2 to current. current is always a prime number. Step 3 would remove from primes 4, 6, 8, 10, 12, 14, 16, 18 and 20 because they are multiples of 2. Then primes = [2, 3, 5, 7, 9, 11, 13, 15, 17, 19] (all of the original numbers except the evens > 2). current becomes the next element in the list, which is 3 (step 4). Because there are more items in the list, we go back to step 3. We take out 6, 9, 12, 15, 18 (multiples of 3); the even numbers, of course, are already out. primes is now [2, 3, 5, 7, 11, 13, 17, 19]. This is the list of prime numbers, but we keep going because there are more values in the list. current becomes 5, and we go back to step 3, and take out 10 and 15 (both of which are already out). current becomes 7, and we take out 14 (already out). We continue until current because 19. We are then out of numbers, so we stop, and return the list of primes from 2..20: [2, 3, 5, 7, 11, 13, 17, 19].

Here is a (buggy) version of the Eratosthenes sieve:

# should return a list of prime numbers from 1..n (including n)

def sieve(n):

if n < 2: #there are no prime numbers < 2

return []

primes = [2] # 2 is the first prime number

for i in range(n): #put all of the numbers into primes initially

primes.append(i)

for current in range(n): # start at current, and remove all multiples of current up to n

for j in range(current,n,current):

primes.remove(j)

return primes

print(sieve(20))

Can you please fix this so it works properly without completely overhauling the code? (please keep the same type of code, just edit it so it is no longer broken) (Here is a screenshot of the properly spaced broken code: https://i.imgur.com/vjzFkRT.png)

Thanks!

Answer 1

There were a few changes I made to your code. I have listed them below :

1) Added an if statement at line 10 because your code was generating the wrong list. What your code did was create a list with 2 as the the first number and then all the numbers from 1 to n, we know this is wrong so thats why I added the if statement so that the generated list contains only numbers from 2 to n.

2) Changed the starting point of the inner loop at line 14 from current to current*current, because python throws an error if we try to delete an element from the list that is not present in it. Lets take the number 6 for example, this will be deleted when current = 2 as it is a multiple of 2 but when current = 3 python will not be able to find 6 in the list and will throw an error, thats why this change was necessary. The if statement inside also complements this.

BELOW IS THE MODIFIED CODE

# should return a list of prime numbers from 1..n (including n)

def sieve(n):
        if n < 2: #there are no prime numbers < 2
                return []

        primes = [2] # 2 is the first prime number
        
        for i in range(n): #put all of the numbers into primes initially
                if i > 2:
                        primes.append(i)
        
        for current in range(2,n): # start at current, and remove all multiples of current up to n
                for j in range(current*current,n,current):
                        if primes.count(j):
                                primes.remove(j)
        
        return primes

print(sieve(20))
print(sieve(40))

OUTPUT