Editor

Python Program to Find the Prime Factors of a Number

Intermediate · Numbers

The prime factors of a number are the prime numbers that multiply together to make it, for example 360 = 2 x 2 x 2 x 3 x 3 x 5. This program finds them by dividing the number by the smallest possible factor again and again.

Program

prime_factors.py
num = 360 # or: num = int(input("Enter a number greater than 1: "))
n = num # work on a copy so num stays unchanged
factors = []
divisor = 2
while divisor * divisor <= n:
while n % divisor == 0:
factors.append(divisor)
n //= divisor
divisor += 1
if n > 1:
factors.append(n) # what is left is itself a prime
print(f"Prime factors of {num}: {factors}")
print(num, "=", " x ".join(str(f) for f in factors))
Output
Prime factors of 360: [2, 2, 2, 3, 3, 5]
360 = 2 x 2 x 2 x 3 x 3 x 5

How it works

  1. The search starts at 2, the smallest prime.
  2. The inner while keeps dividing by the same divisor for as long as it fits, so a prime that appears three times, like 2 in 360, is recorded three times.
  3. Only primes are ever recorded: by the time divisor reaches 4, every 2 has already been divided out, so 4 can no longer divide n.
  4. The loop stops once divisor * divisor is bigger than n; anything above 1 left in n at that point is a prime factor, like the 5 in 360.
  5. " x ".join(...) puts the factors together into the product shown on the last line.

Other ways to write it

Primes with their powers

Primes with their powers
num = 360
n = num
powers = {}
divisor = 2
while n > 1:
while n % divisor == 0:
powers[divisor] = powers.get(divisor, 0) + 1
n //= divisor
divisor += 1
parts = [f"{p}^{k}" if k > 1 else str(p) for p, k in powers.items()]
print(num, "=", " x ".join(parts))
print("Distinct prime factors:", list(powers))
Output
360 = 2^3 x 3^2 x 5
Distinct prime factors: [2, 3, 5]

A dictionary counts how many times each prime divides the number, giving the power form used in maths books: 360 = 2^3 x 3^2 x 5.

Using recursion

Using recursion
def prime_factors(n, divisor=2):
if n == 1:
return []
if n % divisor == 0:
return [divisor] + prime_factors(n // divisor, divisor)
return prime_factors(n, divisor + 1)
for n in [12, 97, 1001]:
print(n, "->", prime_factors(n))
Output
12 -> [2, 2, 3]
97 -> [97]
1001 -> [7, 11, 13]

Each call either takes out one factor or moves on to the next divisor. It is neat, but a large prime would hit Python's recursion limit.

Try it yourself

Find the largest prime factor of 600851475143, a well-known Project Euler puzzle.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises