Python Program to Find Prime Factors of a Number

You can find prime factors of a number in Python by dividing the number repeatedly by integers starting from 2 using a loop and collecting divisors that divide it completely, like this: while n % i == 0: factors.append(i); n //= i.

Examples

Input28

Output[2, 2, 7]

Input13

Output[13]

Input1

Output[]

How to Think About It

To find prime factors, start dividing the number by the smallest prime 2. If it divides evenly, record 2 and divide the number by 2. Repeat until it no longer divides. Then try the next number 3, 4, and so on until the number becomes 1. The recorded divisors are the prime factors.

Algorithm

1

Get the input number n.

2

Start with divisor i = 2.

3

While i * i <= n, do:

4

While n is divisible by i, add i to factors and divide n by i.

5

Increment i by 1.

6

If n is greater than 1 after the loop, add n to factors.

7

Return the list of factors.

Code

python

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

num = 28
print(prime_factors(num))

Output

[2, 2, 7]

Dry Run

Let's trace the number 28 through the code to find its prime factors.

1

Initialize variables

n = 28, factors = [], i = 2

2

Check if i*i <= n

2*2=4 <= 28 is True

3

Check if n % i == 0

28 % 2 == 0 is True, add 2 to factors, n = 28 // 2 = 14

4

Repeat inner while

14 % 2 == 0 is True, add 2 to factors, n = 14 // 2 = 7

5

Repeat inner while

7 % 2 == 0 is False, exit inner loop

6

Increment i

i = 3

7

Check i*i <= n

3*3=9 <= 7 is False, exit outer loop

8

Check if n > 1

n = 7 > 1 is True, add 7 to factors

i	n	factors
2	28	[]
2	14	[2]
2	7	[2, 2]
3	7	[2, 2]
-	7	[2, 2, 7]

Why This Works

Step 1: Start with smallest divisor

We begin checking divisors from 2 because it is the smallest prime number.

Step 2: Divide repeatedly

If the number divides evenly by the divisor, we record it and divide the number to reduce it.

Step 3: Stop when divisor squared exceeds number

We only need to check divisors up to the square root of the number because larger factors would have appeared earlier.

Step 4: Add remaining number if prime

If after division the number is still greater than 1, it means it is a prime factor itself.

Alternative Approaches

Using recursion

python

def prime_factors_recursive(n, i=2, factors=None):
    if factors is None:
        factors = []
    if i * i > n:
        if n > 1:
            factors.append(n)
        return factors
    if n % i == 0:
        factors.append(i)
        return prime_factors_recursive(n // i, i, factors)
    else:
        return prime_factors_recursive(n, i + 1, factors)

print(prime_factors_recursive(28))

Recursion can be elegant but may hit limits for very large numbers.

Using sympy library

python

from sympy import primefactors
print(primefactors(28))

Using a library is fastest and simplest but requires external dependency.

Complexity: O(√n) time, O(log n) space

Time Complexity

The outer loop runs up to the square root of n, and the inner loop divides n by prime factors, making the overall time roughly O(√n).

Space Complexity

The space used is for storing factors, which is at most O(log n) because the number of prime factors grows slowly.

Which Approach is Fastest?

Using the sympy library is fastest for large numbers, but the manual loop method is simple and requires no extra packages.

Approach	Time	Space	Best For
Loop division	O(√n)	O(log n)	Learning and small to medium numbers
Recursion	O(√n)	O(log n)	Elegant code but limited by recursion depth
sympy library	Optimized C code	Depends on implementation	Fastest for large numbers, requires external library