How to Find Prime Factors in Python

To find the prime factors of an integer in Python, repeatedly divide it by prime numbers. This article shows a custom trial-division function, a Sieve of Eratosthenes approach, and the third-party primefac package. The factors are returned as a list, with repeated factors included.

Overview of Prime Factorization

A factor of an integer divides it with no remainder. A prime number is greater than 1 and has exactly two positive factors: 1 and itself. For example, 3, 7, 11, and 13 are prime.

Prime factorization writes an integer greater than 1 as a product of prime numbers. Since 6 = 2 × 3, its prime factors are 2 and 3. A factor can appear more than once: 20 = 2 × 2 × 5, so its prime factors are [2, 2, 5].

Different Approaches to Find Prime Factors in Python

Choose trial division for a small, direct implementation; use a sieve when you also need primes up to a limit; or use primefac when you want a package to provide factorization. The custom function below returns each prime factor with its multiplicity.

Custom Function to Perform Prime Factorization

Trial division tests candidate divisors in ascending order. When a candidate divides the remaining value, the function records it and divides it out before testing again. It is enough to test while the candidate’s square is no greater than the remaining value: if a larger factor remains, its paired factor would already have been found. Any remaining value greater than 1 is prime.

Run this example with the integer 20:

def prime_factors(n):
    if n < 1:
        return None

    factors = []
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1
    if n > 1:
        factors.append(n)
    return factors


print(prime_factors(20))

[2, 2, 5]

The function uses one divisor loop; it does not first generate a list of primes. Its // operation keeps the remaining value an integer. The None result marks unsupported values below 1; prime_factors(1) returns [] because 1 has no prime factors.

Use the Sieve of Eratosthenes to Perform Prime Factorization

The Sieve of Eratosthenes finds all primes up to a limit by marking multiples of each prime, starting with that prime’s square. To factor one integer, build the sieve only up to that integer, then divide out each listed prime as many times as possible. This approach is useful if the prime list will be reused; building a sieve just to factor one value may do extra work. The sieve below returns primes through its inclusive limit. It is a syntax and algorithm example without displayed output.

def primes_up_to(limit):
    if limit < 2:
        return []

    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [number for number, prime in enumerate(is_prime) if prime]


def factor_with_sieve(number):
    if number < 1:
        return None
    factors = []
    for prime in primes_up_to(number):
        while number % prime == 0:
            factors.append(prime)
            number //= prime
    return factors

For more detail about the Sieve of Eratosthenes, see the related guide. As with the custom function, this version returns [] for 1 and None for values below 1.

Use the primefac Module to Perform Prime Factorization

primefac is an external Python package, so it must be installed in the environment that runs your program. Its primefac() function yields prime factors; convert the result to a list when you need to display or store them as a sequence: list(primefac.primefac(20)). This option keeps the factorization logic in the package rather than in a custom function. The package call is shown inline because this article’s self-contained examples do not include or install that external dependency.