eratostenes.py

#!/usr/bin/python
import math
import sys

def is_prime(n):
    """
    Tells if a number is a prime

    This uses the fact that prime numbers greater than 2 and 3 can always
    be written in the form 6k+1 or 6k-1. That is, they are always 'next'
    to a number divisible by 6. (http://primes.utm.edu/notes/faq/six.html)
    So we take 5 which is the one just before the first multiple of 6 (6 itself)
    and test if it can divide the number, then we do the same for 5+2 (or 6+1).
    If none of these works, we go to the next set of possible primes, those
    adjacent to 12 (that's why we increment the possible_prime by 6).

    We do this until we get to a number that can divide it (that is, until we
    get proof that it is not a prime), or until the square root of the number,
    in which case it is a prime.
    """
    if n == 1: return False
    if n < 4: return True # 2 and 3 are prime
    if not n % 2: return False # even numbers are not prime
    if n < 9: return True # we've taken out 4, 6 and 8 (even)
    if not n % 3: return False # multiples of 3 are not prime
    root = int(math.sqrt(n)) # usar o ceil
    possible_prime = 5 #every case before 5 has been treated before this line
    while possible_prime <= root:
        if not n % possible_prime: return False
        if not n % (possible_prime + 2): return False
        possible_prime = possible_prime + 6
    return True

def process(limit):
    """This function calculates all the prime numbers in a range (from 2 to the
    limit you specify).
    """
    result = []
    for i in range(2, limit+1):
        if is_prime(i):
            result.append(i)

    return result

# If the program is directly called, not by another program, then print a list
# of the prime numbers found.
if __name__ == '__main__':
    try:
        limit = int(sys.argv[1])
    except IndexError:
        limit = input('qual o numero limite do calculo a ser feito? ')

    result_list = process(limit)
    for item in result_list:
        print item