primes.py

#!/usr/bin/env python
#
# Find prime numbers
# Author:  Yotam Medini  [email protected] -- Created: 2006/January/29
#

import sys


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


def isPrime(n):
    noFactorFound = True  # we did not find a factor yet.
    d = 2
    # It is enough to check divisors until the square-root  of n.
    # Note that          d <= sqrt(n)
    # if-and-only-if     d*d <= n     - which is easier to compute.
    while d*d <= n and noFactorFound:
        noFactorFound = (n % d != 0)
        d = d + 1
    return (n > 1) and noFactorFound


# Begin program
if len(sys.argv) == 1:
    usage_exit(sys.argv[0], 1)
M = int(sys.argv[1])
n = 2
nPrimes = 0
while n <= M:
    if isPrime(n):
        nPrimes += 1
        sys.stdout.write("Prime[%3d] = %5d\n" % (nPrimes, n))
    n += 1
sys.exit(0)