Sieve Examples

eratosthenes_sieve.py

#!/usr/bin/env python

#############################################
# Eratosthenes's Sieve
#
# see http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
#
# Usage
#  arg1: int Integer limit
#
#############################################

import sys

primes = []
integers = range(2,int(sys.argv[1])+1)

while(True):
    primes.append(integers.pop(0))
    prime = primes[-1]
    integers = [x for x in integers if x%prime!=0]

    if len(integers)==0: break;

    integer = integers[-1]
    if prime^2 > integer: break

print primes