eratos.py

#!/usr/bin/env python
#
# Sieve of Eratosthenes
# Author:  Yotam Medini  [email protected] -- Created: 2006/February/06

import sys

def usage_exit(a0, rc):
    sys.stderr.write(
"""
Usage:
  %s <bound>
"""[1:] % a0)
    sys.exit(rc)


# Mark by False all multipliers of n in the sieve.
# Note that sieve is a list that is being _changed_ here for the caller.
def mark_mults(sieve, n):
    mult = n*n
    while mult < len(sieve):
        sieve[mult] = False
        mult += n


# Begin program
if len(sys.argv) != 2:
    usage_exit(sys.argv[0], 1)
M = int(sys.argv[1])
sieve = (M + 1)*[True]
n_primes = 0
n = 2
while n <= M:
    if sieve[n]:
        n_primes += 1
        sys.stdout.write("P[%3d] = %5d\n" % (n_primes, n))
        mark_mults(sieve, n)
    n += 1
sys.exit(0)