Prime factors of a number in Python

Every whole number greater than 1 can be written as a product of prime numbers in exactly one way (apart from the order of the factors). For example, 360 = 2 × 2 × 2 × 3 × 3 × 5. These primes are the prime factors of 360.

The program

n = int(input("Enter a number: "))

if n < 2:
    print("Enter a whole number greater than 1.")
else:
    factors = []
    number = n
    divisor = 2
    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        divisor += 1
    if number > 1:
        factors.append(number)

    print("Prime factors:", factors)
    print(n, "=", " × ".join(str(f) for f in factors))

Typed in this example: 360. Press Run to type your own.

Enter a number: 360
Prime factors: [2, 2, 2, 3, 3, 5]
360 = 2 × 2 × 2 × 3 × 3 × 5

How it works

• The inner while divides by the same divisor as many times as possible. 360 becomes 180, 90 and 45 (three 2s), then 15 and 5 (two 3s).
• The divisor 4 never divides the number, even though 4 is not prime. By the time the loop reaches 4, all the 2s have already been removed. In the same way, every divisor that divides the number is prime.
• The loop stops when divisor * divisor is bigger than what is left. If more than 1 is left at that point, it must be a prime, so it is added at the end. For 360 that last factor is 5.
• Stopping at the square root makes the program fast. For a large prime such as 1,000,003, the loop runs about 1,000 times instead of a million.

To check whether a single number is prime, see the prime number check.

With powers

Counter counts how many times each factor appears, so you can write 360 as 2³ × 3² × 5:

from collections import Counter


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


for n in [360, 97, 1001, 1024]:
    counts = Counter(prime_factors(n))
    parts = [f"{p}^{k}" if k > 1 else str(p) for p, k in counts.items()]
    print(n, "=", " × ".join(parts))

360 = 2^3 × 3^2 × 5
97 = 97
1001 = 7 × 11 × 13
1024 = 2^10