Prime factorization using list comprehension in Python

Question

How to write a function which returns a list of tuples like (c_i, k_i) for n such that n = c₁^k₁ c₂^k₂ ... c_i^k_i is a prime number?

For example: 12600 = 2³ · 3² · 5² · 7¹

Desired output: [(2, 3), (3, 2), (5, 2), (7, 1)]

I know how to do it with while but is it possible to do it using list comprehension? Efficiency is not required in this task.

# naive function 
def is_prime(n):
    return n > 1 and all(n % i != 0 for i in range(2, n))

# while version
def factorization_while(n):
    res = []
    for i in range(1, n + 1):
        if is_prime(i):
            j = 0
            while n % i == 0:
                n = n // i
                j += 1
            if j != 0:
                res.append((i, j))
    return res

# list comprehension version
def factorization(n):
    return [
        (i, j) for i in range(1, n + 1) if is_prime(i) \
        and n % i == 0 ... # add smth
    ]

Answer 1

Factorization to list of tuples by list comprehension? OK. I have written one by one several versions that solve the above problem, which I don't want to clutter the page with; you can find few of them as addendum in the Tio link below. The main challenge with this assignment is the lack of a while or until constructor in list comprehension, which we have to work around somehow. This is my solution:

n=6694380 # e.g.
print([(d,e)for i,d in enumerate([2]+list(range(3,int(n**.5)+1,2))) # divisor,init
     if(e:=len(                                                     # exponent
               [q:=q if q%d else q//d                               # quotient
                                     for j in range(30)             # 2ⁿᵈ init
                                                      if not(q:=q if i+j else n)%d
                                                                    # 1ˢᵗpass test
                ]
               )
        )
       ]+([(q,1)]if q-1 else[])    # (+ prime quotient)
      )

# Output: [(2, 2), (3, 3), (5, 1), (7, 2), (11, 1), (23, 1)]

To try it, as well as for a deeper explanation see this demo in Tio (about ½ minute demo run).

A little criticism to the author of this assignment: The challenge to write a list-comprehension generator of prime decomposition and additionally to tuples detecting how many times a given prime number is repeated in the decomposition is really interesting call, but in such a case to assume that the generated sniplet would form the body of a dedicated function does not make any sense; the solution using list comprehension forms a fully functional part of the code that can lie anywhere in it and that does not need a function as an external callable unit to be used.

Finally, a dig at others here: this assignment does not ask you to write a library import and winningly call it. Otherwise this one would be the proper solution to find prime factors (not yet associated into tuples):

from primepy import primes
print(primes.factors(n:=6543210))

# Output = [2, 3, 5, 19, 953]

Answer 2

OP's code is extremely inefficient.

That is not how list comprehension should be used. That is not how prime factorization works.

There is absolutely no need to check for primeness during prime factorization. Number a is a factor of b if not a % b. To do prime factorization, first we need to process all powers of two in the factors, all prime numbers are odd except two, so we only need to brute force odd numbers until the square of the iteration variable is greater than n.

This is how it should be done:

def factorize(n):
    factors = []
    while not n % 2:
        factors.append(2)
        n //= 2

    i = 3
    while i**2 <= n:
        while not n % i:
            factors.append(i)
            n //= i
        i += 2
    
    return factors if n == 1 else factors + [n]

---

Update

List comprehension simply doesn't mesh with prime factorization. They can be hacked together, but the result is bound to be too complex and too inefficient to be good.

But the second point about the output format is valid. Indeed the format I used in my code is inefficient. This is trivially fixable:

def factorize(n):
    factors = (
        [(2, exp)] 
        if (exp := (n & -n).bit_length() - 1) 
        else []
    )

    i = 3
    while i**2 <= n:
        exp = 0
        while not n % i:
            exp += 1
            n //= i

        factors.append((i, exp))
        i += 2

    return factors if n == 1 else factors + [(n, 1)]

---

This was clearly for demonstration purposes and wasn't meant for practical use.

But I just spent less than two minutes to fix the code:

from math import isqrt

def factorize(n):
    factors = (
        [(2, exp)] 
        if (exp := (n & -n).bit_length() - 1) 
        else []
    )

    if exp:
        n >>= exp
    
    i = 3
    while i <= isqrt(n) + 1:
        exp = 0
        while not n % i:
            exp += 1
            n //= i

        if exp:
            factors.append((i, exp))

        i += 2

    return factors if n == 1 else factors + [(n, 1)]

Answer 3

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).