Welcome, guest | Sign In | My Account | Store | Cart

A simple implementation of the Sieve of Eratosthenes in Python. The code should be self-explanatory, but I've added a docstring and some comments just in case.

Constructive criticism is of course appreciated.

Python, 29 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def primeSieve(x):
    '''
       Generates a list of odd integers from 3 until input, and crosses
       out all multiples of each number in the list.

       Usage:

       primeSieve(number) -- Finds all prime numbers up until number.

       Returns: list of prime integers (obviously).

       Time: around 1.5 seconds when number = 1000000.

       '''
    
    numlist = range(3, x+1, 2)
    counter = 0 # Keeps count of index in while loop
    backup = 0 # Used to reset count after each iteration and keep count outside of while loop
    for num in numlist:
        counter = backup
        if num != 0:
            counter += num
            while counter <= len(numlist)-1: # Sifts through multiples of num, setting them all to 0
                    numlist[counter] = 0
                    counter += num
        else: # If number is 0 already, skip
            pass
        backup += 1 # Increment backup to move on to next index
    return [2] + [x for x in numlist if x]
Created by Assil Ksiksi on Sun, 27 Nov 2011 (MIT)
Python recipes (4591)
Assil Ksiksi's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks