python primes

#!/usr/bin/env python
# Filename:                primes.py
# Description:             Returns all primes less than N
# Supported Langauge(s):   Python 2.5.x
# Time-stamp:              <2007-12-10 00:38:14> 
# -------------------------------------------------------
# I. Find all primes <100 using the Sieve of Eratosthenes:
# 
# By the fundamental theorem of arithmetic: 
#  * every postive integer is a prime xor a composite
#  * every composite can be written as the product of primes 
#  * if n is a composite, then n has a prime divisor <= sqrt(n)
#
# So we'll start with a list of primes whose prime factor is less
# than sqrt(100), or 10.  These primes will be 2,3,5,7.
# 
# To use the sieve we do the following:  
# 
# * integers divisible by 2 (besides 2) are deleted
# 
# * since 3 is the first integer greater than 2 that is left,  
#   all integers divisible by 3 (besides 3) are deleted
# 
# * since 5 is the next integer after 3 that is left, all integers
#   divisible by 5 (besides 5) are deleted
# 
# * since 7 is the next integer after 5 that is left, all integers
#   divisible by 7 (besides 7) are deleted
# 
# * since all composite integers not exceeding 100 are divisible
#   by 2,3,5,7 all remaining integers except 1 are prime.  
# 
# Runtime:  n * sqrt(n)
# -------------------------------------------------------

from math import sqrt
from math import ceil

def divides(a, b):
    return a % b == 0

def sprimes(n):
    integers = []  
    for i in range(2, n): 
        integers.append(i)

    max_factor = int(ceil(sqrt(n))) 
    factors = integers[:max_factor] 

    for factor in factors:
        for integer in integers:
            if (divides(integer, factor) and (integer != factor)):
                integers.remove(integer)
                if (integer in factors):
                    factors.remove(integer)
    return integers 

print sprimes(1000)

# -------------------------------------------------------
# II. find all primes <100 using Wilson's theorem:
# 
#  p>1 is a prime iff fact(p-1) == -1 (mod p)
# 
# As per:  http://en.wikipedia.org/wiki/Wilson's_theorem
# 
# Translating modular arithmetic into Python:
#  http://www.muppetlabs.com/~breadbox/txt/rsa.html#3
# 
# As the above states "27 == 3 (mod 12)" in Math would be 
# "27 % 12 == 3" in Python.  Taking it to the next step:
# "fact(p-1) == -1 (mod p)" would be "fact(p-1) % p == -1".
# However, since a programming language's modulo returns an
# integer greater than or equal to zero I won't get a -1 so
# I'll use "fact(n-1) % n == n-1".  

def fact(n):
    f = 1
    while (n > 0):
        f = f * n;
        n = n - 1;
    return f;

def prime(n):
    return (fact(n-1) % n) == (n-1)

def wprimes(n):
    integers = []  
    for i in range(2, n):
        if prime(i):
            integers.append(i)
    return integers

print wprimes(1000)
        
# -------------------------------------------------------
# The Sieve of Eratosthenes ran faster than Wilson's theorem,
# probably because of the factorial (try it on 1000)