Simple python code to solve Factorization Problems -TRAIL and DIVISION METHOD with PRIME SIEVE

TRAIL and DIVISION METHOD with PRIME SIEVE .py

""" TRAIL and DIVISION METHOD with PRIME_SIEVE """

def primes_sieve(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False
    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n == 1: return [1]
    primes = primes_sieve(int(pow(n,0.5)) + 1)   # Prime factor is always less than SQRT(n)+1
    prime_factors = []
 
    for p in primes:
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1: prime_factors.append(n)
 
    return prime_factors
    
t = trial_division(600851475143)
print t