56Composite
- Factors
- 2, 2, 2, 7
Find Prime Factors in Python
What you’ll learn
- What prime factors mean and how they rebuild a number.
- A simple trial division method and a faster variant.
- How to handle invalid inputs like n < 2 safely.
Overview
Prime factorization breaks a number into prime pieces. Example: 56 = 2 * 2 * 2 * 7.
Two approaches
Straightforward and optimized trial division.
Live preview
Type 56, 17, or 360 and see factors.
Input guards
Require n >= 2 to avoid bad loops.
Prerequisites
Loops, modulo, and basic prime number idea.
- Use
whileandforloops. - Know
n % d == 0means d divides n.
What are prime factors?
Prime factors are prime numbers multiplied together to rebuild n.
Repeated factors are normal (e.g., 2 appears three times in 56).
Why trial order works
Trying smaller divisors first strips their factors, so composite candidates stop dividing naturally.
Check
Multiplying printed factors always reconstructs original n (for n >= 2).
Quick examples
17Prime
- Factors
- 17 only
360Many factors
- Starts
- 2, 2, 2, 3, 3, 5...
Live preview
Uses optimized factorization (2s first, then odd divisors).
Algorithm (trial division)
Goal: print prime factors in non-decreasing order for n >= 2.
Validate n
Reject n < 2.
Try divisors
For each i, divide while x % i == 0 and print i.
Finish when x is 1
All factors are extracted.
📜 Pseudocode
Pseudocode
procedure display_prime_factors(n):
if n < 2:
stop
x = n
for i from 2 while i <= x:
while x mod i == 0:
output i
x = x / i1
Straightforward trial division
Simple readable method using nested loops.
python
def divides_evenly(a: int, b: int) -> bool:
return a % b == 0
def display_prime_factors(n: int) -> None:
if n < 2:
print(f"Enter an integer n >= 2 (got {n}).")
return
print(f"Prime factors of {n} are:", end=" ")
x = n
i = 2
while i <= x:
while divides_evenly(x, i):
print(i, end=" ")
x //= i
i += 1
print()
display_prime_factors(56)2
Faster trial division (2 then odd up to sqrt)
Fewer divisor checks by handling 2 separately and testing odd candidates only.
python
def display_prime_factors_fast(n: int) -> None:
if n < 2:
print(f"Enter an integer n >= 2 (got {n}).")
return
print(f"Prime factors of {n} are:", end=" ")
x = n
while x % 2 == 0:
print(2, end=" ")
x //= 2
i = 3
while i * i <= x:
while x % i == 0:
print(i, end=" ")
x //= i
i += 2
if x > 1:
print(x, end=" ")
print()
display_prime_factors_fast(56)Notes
Sieve for many queries. If factoring many numbers, precomputed primes are faster.
Type safety. Python ints are arbitrary precision, so no overflow worries here.
Related topics. Prime check, composite numbers, and GCD use similar divisor logic.
❓ FAQ
A prime factor is a prime number that divides the given number evenly.
Trying factors in order and dividing repeatedly ensures composite candidates stop dividing after smaller primes are removed.
To capture repeated factors like 2, 2, 2 in 56.
Prime factorization here is defined for n >= 2.
Yes, factors print in non-decreasing order.
It tests fewer candidates by stopping around sqrt(x) and handling leftover prime at the end.
🔄 Input / output examples
Replace value passed to function call and observe printed factors.
| n | Printed factors |
|---|---|
| 56 | 2 2 2 7 |
| 17 | 17 |
| 12 | 2 2 3 |
| 1 | Error message (n >= 2 required) |
Edge cases
n = 0
Reject input
Guard avoids infinite divide loop risks.
n = 1
No factorization
Prime factorization starts at n >= 2.
Square values
Repeated factors expected
36 -> 2 2 3 3.
⏱️ Time and space complexity
| Version | Time (single n) | Extra space |
|---|---|---|
| Basic trial division | Worst near O(n) | O(1) |
| sqrt-bounded version | Typical O(sqrt(n)) | O(1) |
Summary
- Prime factors multiply back to original n.
- Use nested division loops and guard n >= 2.
- sqrt-bounded variant is faster for larger inputs.
Did you know?
Every integer greater than 1 can be written as a product of primes in exactly one way (ignoring order).
About the author
8 people found this page helpful