Odd prime factors of large numbers

Question

I wrote and use this function to create prime number factors:

import numpy as np from math import sqrt def primesfrom3to(n): """ Returns a array of primes, p < n """ assert n>=2 sieve = np.ones(n/2, dtype=np.bool) for i in xrange(3,int(n**0.5)+1,2): if sieve[i/2]: sieve[i*i/2::i] = False return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1] def primefactors(tgt,verbose=True): if verbose: print '\n\nFinding prime factors of: {:,}'.format(tgt) primes=primesfrom3to(sqrt(tgt)+1) if verbose: print ('{:,} primes between 2 and square root of tgt ({:.4})'. format(len(primes),sqrt(tgt))) return [prime for prime in primes if not tgt%prime] 

If I call it Project Euler # 3 , it successfully creates a list of different prime numbers:

 >>> print primefactors(600851475143) Finding prime factors of: 600,851,475,143 62,113 primes between 2 and square root of tgt (7.751e+05) [71, 839, 1471, 6857] 

This is consistent with what Wolfram Alpha produces for key factors. (And the biggest is the correct answer to Project Euler # 3)

Now let's say that I want the factors of this number x 1e6:

 >>> print primefactors(600851475143*1000000) Finding prime factors of: 600,851,475,143,000,000 39,932,602 primes between 2 and square root of tgt (7.751e+08) [2, 5, 71, 839, 1471, 6857] 

For this more Wolfram Alpha produces :

 2**6 * 5**6 * 71 * 839 * 1471 * 6857 

Is there an easy way to change my code, which I can calculate the values ​​of 2 and 5 as the main factors of a larger number?

(I'm interested in the source code or the algorithm for this - not a pointer to a library that will do this for me, thanks!)

Answer 1

Regards, this is simpler (and much faster and more efficient):

 from collections import defaultdict from math import sqrt def factor(n): i = 2 limit = sqrt(n)    while i <= limit:   if n % i == 0:     yield i     n = n / i     limit = sqrt(n)     else:     i += 1 if n > 1:   yield n def pfac(num): d=defaultdict(int)   for f in factor(num):       d[f]+=1   terms=[]   for e in sorted(d.keys()):       if d[e]>1:           terms.append('{:,}^{}'.format(e,d[e]))       else:           terms.append('{:,}'.format(e))   print ' * '.join(terms),'=','{:,}'.format(num)          pfac(600851475143*1000000-1) pfac(600851475143*1000000) pfac(600851475143*1000000+1) 

Print

 83 * 127 * 57,001,373,222,939 = 600,851,475,142,999,999 2^6 * 5^6 * 71 * 839 * 1,471 * 6,857 = 600,851,475,143,000,000 3^2 * 19 * 103 * 197 * 277 * 16,111 * 38,803 = 600,851,475,143,000,001 

Answer 2

The traditional way to do this is to split each major factor in turn, and then recursively according to your factorization method. This will be, in general, faster than sifting for all primes, because you only care about the (few) primes that actually divide your number.

Of course, there are many, many better simple factorization algorithms than trial division; people usually use something like a square sieve for a wide range of numbers, with the Pollard method rho at the small end and a sieve with a number field on the large. All this is much more complicated.

---

Since you sift through all primes in advance, the efficiency of your algorithm is not important to you. Given that it is easiest to work out pluralities ex post facto, as @tobias_k wrote. You can also break it down into a separate function as

 def multiplicity(n, p): i = 0 while not n % p: i, n = i+1, n/p return i 

and then

 >>> n = 600,851,475,143,000,000 >>> n = 600851475143000000 >>> factors = [2, 5, 71, 839, 1471, 6857] >>> [(f, multiplicity(n,f)) for f in factors] [(2, 6), (5, 6), (71, 1), (839, 1), (1471, 1), (6857, 1)] 

Answer 3

Once you have certain basic factors, you can do something like this:

 factors = [] for f in distinct_prime_factors: while n % f == 0: factors.append(f) n /= f 

Now factors will contain a list of all the simple factors.