jib.py

jib.py

# getPrimes takes one argument, maxNum, and returns all prime numbers
# that exist between 2 and maxNum using the sieve of erasmus algorithm
def getPrimes(maxNum):
    primes = []

    # create a list of all possible prime numbers between 2 and maxNum
    candidates = [i for i in xrange(2, maxNum)]

    # while there are possible prime numbers remaining
    while len(candidates) > 0:
        # take the first number from the candidates list. This must be
        # a prime number. If this is the first time through the loop
        # then it's 2 and 2 is a prime number. If it is a subsequent
        # run through the loop then it must be a prime number of else
        # it would have been removed by our algorithm.
        new_prime = candidates.pop(0)

        # add the new prime to the results list
        primes.append(new_prime)

        # Remove all numbers from the candidates list that are divisible
        # by new_prime. A number that is disible by a prime number cannot
        # itself be a prime number
        candidates = [i for i in candidates if i % new_prime != 0]

    return primes

print getPrimes(20000)