Prime Factorisation in Python

Question

how can I count the occurrences of the factors when doing the Prime Factorisation?

e.g. factorization(504), output = [(2,3), (3,2), (7,1)] instead of [2, 2, 2, 3, 3, 7]

Here is my code:

def factorization(n):
    prime = 2
    factor = []
    while prime <= n:
        if n % prime == 0:
            factor.append(prime)
            n = n / prime
        else:
            prime += 1
    a = factor.count(prime in factor)
    
    return print(factor, a)

`return print(...)` returns `None` because `print` doesn't return anything. Returning is _not the same as printing_ — Pranav Hosangadi, Mar 18 '22 at 15:46
Does this answer your question? [How can I count the occurrences of a list item?](https://stackoverflow.com/questions/2600191/how-can-i-count-the-occurrences-of-a-list-item) — LeopardShark, Mar 18 '22 at 15:46

score 1 · Answer 1 · answered Mar 18 '22 at 15:48

This is exactly what collections.Counter() will do for you:

from collections import Counter
prime_factors = [2, 2, 2, 3, 3, 7]
Counter(prime_factors)

-> Counter({2: 3, 3: 2, 7: 1})

To get the output you specifically showed:

counted_factors = Counter(prime_factor)
list(counted_factors.items())

-> [(2, 3), (3, 2), (7, 1)]

Bao Huynh Lam · Answer 2 · 2022-03-18T16:12:05.433

You can use a = [(distinct_prime, factor.count(distinct_prime)) for distinct_prime in set(factor)]

This is using list comprehension to create a list of tuples. However, you only want to include distinct primes from the factor list in your a, so I put it into set(factor)

Another way is to use a dictionary to count frequency, then convert the dictionary into list of tuples

freq = {}
for num in factor:
  freq[num] = freq.get(num, 0) + 1
a = list(freq.items())
# You can do an additional sorting step if you wish to
a.sort()

Prime Factorisation in Python

2 Answers2