Euler 3

#!/usr/bin/env python
# http://projecteuler.net/index.php?section=problems&id=3
# Find the largest prime factor of 600851475143

# Disappointingly, it's quicker without a sieve.
# 14 seconds, as opposed to several minutes and still no sieve.

import time
import math

# I admit this algorithm came from the question 7 PDF.
def CHEATisPrime(n):
    if (n == 1):
        return False
    elif (n < 4):
        return True
    elif (n % 2) == 0:
        return False
    elif (n < 9):
        return True
    elif (n % 3) == 0:
        return False
    else:
        r = math.floor( math.sqrt(n) )
        f = 5
        while f <= r:
            if (n % f) == 0:
                return False
            elif (n % (f+2) ) == 0:
                return False
            f += 6
    return True

def primeSieve(n):
    """Generates and returns a list of primes, up to n"""
    a = range(1, n+1)
    a.remove(1)
    position = 0

    rootn = math.sqrt(n)

    while a[position] <= rootn:
        multiples = range(a[position]*2, n+1, a[position])
        for i in range(len(multiples)):
            try:
                a.remove(multiples[i])
            except:
                pass
        position += 1

    print 'Sieve complete'
    return a

# This one, however, is mine. :D
def isPrime(n):
    """Returns whether the number is prime"""
    for i in range(len(primes)):
        if (n % primes[i] == 0):
            return False
    return True


start = time.time()

# Insert python code here
bignumber = 600851475143
root = math.sqrt(bignumber)
#primes = []primeSieve(root)
done = False
factor = 0

# Iterate through the prime numbers until we reach sqrt(number),
# saving the largest factor so far
for i in range(math.sqrt(bignumber), 0, -1):
    if CHEATisPrime(i):
        if (bignumber % i) == 0:
            factor = i
            break

print 'The largest prime factor of ' + `bignumber` + ' is ' + `factor`

end = time.time()
print 'This took ' + `end-start` + ' seconds to calculate.'