Question

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))

Using PyCharm, under lab8, under Directory exercise, create a Python file called erat.py, and add the function above to it. Test the function with print(sieve(20)), as shown above.

Pycharm allows you to run programs in debug mode so that you can see the value of variables. First, we need to decide where we want to start looking, maybe the for current loop, the outer loop. In my code, that is on line 8. In the Pycharm editor window, go to the grey area to the right of the line number with the outer for loop, and right click. A red circle should appear. This is called a breakpoint. When you debug your program, the program will stop before executing this statement. To start debug, right click in the code area, and choose Debug instead of Run:

The program should begin running. A debug window should appear in the lower part of your PyCharm window that shows you the value of your variables. It should look something like this:

The variable i is set from the previous loop. primes is not filled with the correct values, but n is correct.

When debugging, you can continue running the program, or stop. To stop, press the red square. Don’t do that now (if you did, just debug again, and get back to the screen above). Instead, perform the next step, in the program by clicking the “Step Into My Code” icon:

current should appear with a value of 0, and the line number to be executed next should be 9 now. Play around with these buttons to see what happens as you execute the sieve function.

There could be other problems, but one problem we have already noticed is that primes is filled with incorrect values. This happened in the first for loop. Before the nested for loops, primes should be [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]. Use the debugger to figure out what went wrong, and fix that problem.

Instead of using the debugger, you can also add print statements to determine the values of the variables. Make sure you label all of the values, or it will be difficult to determine what values are being printed. For example, you might be the following inside the inner loop:

print('right now, current is', current, 'j is ', j, 'primes is', primes)

print('removing', j)

to see the value of the variables as you loop through.

Debug sieve, fix it, and run the tests for sieve. You will need to change the values within range statements, and add an if statement to make the code run correctly. You should not need to change anything else. Test your solution, and submit it.

Answer 1

Code screenshot:

erat.py

# 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(3,n+1): #put all of the numbers into primes initially
       primes.append(i)
   for current in primes:
       # start at current, and remove all multiples of current up to n
       for j in range(2*current,n+1,current):
           if j in primes:
               primes.remove(j)
   return primes
print(sieve(20))

output screenshot: