Skip to main content

How to Find Prime Factors of an Integer in Python

Prime factorization is the process of breaking down an integer into a sequence of prime numbers that, when multiplied together, produce the original number. For example, the prime factors of 60 are 2, 2, 3, 5 (2 × 2 × 3 × 5 = 60).

This guide explores two primary ways to find prime factors in Python: writing a custom Trial Division algorithm for understanding the logic, and using the SymPy library for high-performance scientific computing.

Understanding Prime Factorization​

According to the Fundamental Theorem of Arithmetic, every integer greater than 1 is either a prime number itself or can be represented as the product of prime numbers in a unique way.

  • Prime Number: A number greater than 1 that has no positive divisors other than 1 and itself (e.g., 2, 3, 5, 7, 11).
  • Composite Number: A number that can be divided by numbers other than 1 and itself.

Finding these factors is crucial for fields like cryptography (RSA encryption relies on the difficulty of factoring large numbers) and number theory.

Method 1: Custom Trial Division Algorithm​

The most straightforward approach is Trial Division. We iterate through possible divisors, checking if they divide the number evenly.

The Strategy:

  1. Divide by 2 repeatedly until the number is odd.
  2. Iterate through odd numbers starting from 3.
  3. Stop checking when the square of the divisor is greater than the remaining number (optimization).
  4. If any number remains greater than 2, it is a prime factor itself.
def get_prime_factors(n):
    """
    Returns a list of prime factors for integer n.
    """
    factors = []
    
    # Step 1: Handle the factor 2 (the only even prime)
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
        
    # Step 2: Iterate through odd numbers starting from 3
    # We only go up to the square root of n to optimize performance
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n = n // divisor
        divisor += 2 # Skip even numbers
        
    # Step 3: If n > 2, the remaining n is a prime factor
    if n > 2:
        factors.append(n)
        
    return factors

# ✅ Example Usage
number = 315
result = get_prime_factors(number)
print(f"Prime factors of {number}: {result}")

number_large = 100
print(f"Prime factors of {number_large}: {get_prime_factors(number_large)}")

Output:

Prime factors of 315: [3, 3, 5, 7]
Prime factors of 100: [2, 2, 5, 5]
note

You do not need to explicitly check if the divisor is prime in the loop. By dividing out small factors (like 2 and 3) as you find them, you ensure that you will never be able to divide by a composite number (like 4, 6, or 9) because its prime components have already been removed.

For scientific computing, robust error handling, or dealing with large integers, the sympy library is preferred over writing your own loops. It uses highly optimized algorithms (like Pollard's rho or Elliptic Curve Method).

Installation:

pip install sympy

Usage:

import sympy

number = 315

# ✅ primefactors returns a list of unique factors (sorted)
unique_factors = sympy.primefactors(number)
print(f"Unique Prime Factors: {unique_factors}")

# ✅ factorint returns a dictionary {factor: multiplicity}
# This represents 3^2 * 5^1 * 7^1
factor_map = sympy.factorint(number)
print(f"Detailed Factors: {factor_map}")

Output:

Unique Prime Factors: [3, 5, 7]
Detailed Factors: {3: 2, 5: 1, 7: 1}
tip

Use sympy.factorint if you need to know how many times a factor appears (multiplicity), which is useful for calculating the Least Common Multiple (LCM) or Greatest Common Divisor (GCD).

Optimization and Edge Cases​

When implementing your own algorithm, keep these considerations in mind:

The Square Root Optimization​

In Method 1, we used the condition while divisor * divisor <= n. If a number n is composite, it must have a factor less than or equal to sqrt(n). If we check all numbers up to sqrt(n) and find no factors, the remaining number is prime. This reduces the time complexity significantly compared to iterating up to n.

Handling Invalid Inputs​

Prime factorization applies to integers greater than 1. You should handle negative numbers, floats, or 1.

def safe_prime_factors(n):
    # ⛔️ Handling Edge Cases
    if not isinstance(n, int):
        raise TypeError("Input must be an integer.")
    if n < 2:
        return [] # 0 and 1 do not have prime factors
    
    # ... (same algorithm from Method 1 here) ...

    factors = []
    
    # Step 1: Handle the factor 2 (the only even prime)
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
        
    # Step 2: Iterate through odd numbers starting from 3
    # We only go up to the square root of n to optimize performance
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n = n // divisor
        divisor += 2 # Skip even numbers
        
    # Step 3: If n > 2, the remaining n is a prime factor
    if n > 2:
        factors.append(n)
        
    return factors

# ✅ Example Usage
number = 0
print(f"Prime factors of {number}: {safe_prime_factors(number)}")

number = 1
print(f"Prime factors of {number}: {safe_prime_factors(number)}")

number = 315
print(f"Prime factors of {number}: {safe_prime_factors(number)}")

Output:

Prime factors of 0: []
Prime factors of 1: []
Prime factors of 315: [3, 3, 5, 7]

Conclusion​

To find prime factors in Python:

  1. Use Method 1 (Trial Division) for simple scripts, coding interviews, or learning purposes. It relies on dividing by 2, then odd numbers up to sqrt{n}.
  2. Use Method 2 (SymPy) for production-grade applications, mathematical research, or when working with very large integers where performance is critical.

Table of Contents