Factorization Problems

""" 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

Fermat Theorem

import math

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

n =  80646413

a = int(math.floor(math.sqrt(n)))
b = 0

while(True):
    b = a*a - n
    t = b**(1/2)
    if b == t*t:
        b = t
        break
    a = a+1
   
print 'the factor are ',gcd(a+b,n),gcd(a-b,n)

# u^2 - v^2 = n
# (u+v)(u-v) = n
# to find 'u' take floor(sqrt(n))