Simple 10 lines of python code to solve Factorization Problem (Trail and Division Method with Prime Sieve) with example Get link Facebook X Pinterest Email Other Apps Simple 10 lines python code to solve Factorization Problem (Trail and Division Method with Prime Sieve) with example """ 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 Comments
Comments
Post a Comment