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: