Prime Factorization - List

Prime factorization - list

A simple trial division:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

with O(sqrt(n)) complexity (worst case). You can easily improve it by special-casing 2 and looping only over odd d (or special-casing more small primes and looping over fewer possible divisors).

I have a Python list of the prime factors of a number. How do I (pythonically) find all the factors?

Instead of a list of exponents, consider simply repeating each prime factor by the number of times it is a factor. After that, working on the resulting primefactors list-with-repetitions, itertools.combinations does just what you need -- you'll just require the combinations of length 2 to len(primefactors) - 1 items included (the combinations of just one are the prime factors, that of all of them will be the original number -- if you want those too, just use range(1, len(primefactors) + 1) instead of the range(2, len(primefactors)) which my main suggestion would use).

There will be repetitions in the results (e.g., 6 will appear twice as a factor of 12, since the latter's primefactors will be [2, 2, 3]) and they can of course be weeded out in the usual ways (i.e. sorted(set(results)) for example).

To compute primefactors given listOfAllPrimes, consider for example:

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors

Create all possible factorisations from a prime factor list in Python

Your task is to determine the multiplicative partition of a number. Google should point you where you need to go. Stack Overflow already has an answer.

Prime factorization using list comprehension in Python

I don't think this should be too hard. You don't actually need to modify n to find its prime factors, they're all completely independent of each other. So just iterate through the appropriate primes, and find the maximum power that works!

from math import log

def prime_factors(n):
    return [(prime, max(power for power in range(1, int(log(n, prime))+1)
                              if n % prime**power == 0))
            for prime in range(2, n+1) if n % prime == 0 and isprime(prime)]

There are a few ways you might improve this further. You could use itertools.takewhile on an infinite generator of powers (e.g. itertools.count), as once you find the first power such that prime**power is not a factor of n, none of the later ones will be either. That would allow you to avoid the log call.

And there are a whole bunch of ways to efficiently iterate over the primes (see for instance, the very simple generator suggested here, or higher performance versions that you can find in the answers to a few different questions here on SO).

Prime factorization using list comprehension

Here's how I'd do it:

pfactors :: Integer -> [Integer]
pfactors n = [ p
             | p <- [2..n]                                  -- Possible factors
             , [d | d <- [1..p], p `mod` d == 0] == [1,p]   -- Are prime 
             , _ <- [ p | i <- [1..n], n `mod` p^i == 0] ]  -- Divisible powers

It's essentially the solution you have, but the difference is that it has an extra list comprehension at the end which contains as many elements as p factors into n.

Disclaimer I really wouldn't do it like this in reality.

EDIT I felt dirty writing the above, so for reference, this is something closer to what I would write:

pfactors' :: Int -> [Int]
pfactors' = unfoldr firstFactor
  where
    firstFactor n =
        listToMaybe [(f, n `div` f)
                    | f <- [2..n]
                    , n `mod` f == 0]

Dependencies: Data.List (unfoldr), Data.Maybe (listToMaybe)

---

Related Topics