Thursday, May 30, 2013

A simple list manipulation - Computing primes using Sieve of Eratosthenes process

I am incredibly dumb that I had to wrestle with this problem for a long time before being able to solve it. But the experience has been invaluable.

The Problem:

Initialize n to be 1000. Initialize numbers to be a list of numbers from 2 to n, but not including n. With results starting as the empty list, repeat the following as long as numbers contains any numbers.
1. Add the first number in numbers to the end of results.
2. Remove every number in numbers that is evenly divisible by (has no remainder when divided by) the number that you
had just added to results.

How long is results?

The Solution (It is ugly!)

n  = 1000 
numbers = range(2, n)
results = []
while numbers:
    i = numbers[0]
    results.append(i)
    for number in numbers:
        if number % i == 0:
            numbers.remove(number)

print numbers
print len(results)


It looks like this computes the primes less than n, by a process known as Sieve of Eratosthenes. Below is another, more elegant and pythonic way to do it.

n = 1000
numbers = range(2, n)
results = []

while numbers != []:
    results.append(numbers[0])
    numbers = [n for n in numbers if n % numbers[0] != 0]

print len(results)

I was stuck with infinite loops with my original program before I stumbled upon pythontutor.org and saw the execution step by step. Below is the visualized execution of my program.