15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Prime factorization by trial division tries candidate divisors d from 2 upward. While d divides the remaining number, record d and divide it out. Stop when d × d exceeds what remains, then record any leftover value above 1 as the last prime. It takes O(sqrt(n)) time and O(1) extra space.
| Method | Trial division: try d = 2, 3, 4, ... and divide out each d fully |
|---|---|
| Loop condition | d × d <= remaining, using the shrinking remaining value; keep <= so 49 tests 7 |
| Last step | If remaining > 1, append it as the final prime factor |
| Time | O(sqrt(n)) for factorization and for a primality test |
| Extra space | O(1) beyond the returned list of k factors |
| The number 1 | Neither prime nor composite; outside factorize(n) |
A positive divisor of a positive integer n is a positive integer d such that:
n mod d = 0
For example, 2 divides 84 because 84 mod 2 = 0.
A number is:
1 and has exactly two positive divisors: 1 and itself.1 and is not prime.1.So:
2 is prime.49 is composite because 7 × 7 = 49.1 is neither. It does not satisfy the “greater than 1” part of the prime definition.We will use two related operations:
A prime factorization groups repeated factors as powers. For example, if we find [2, 2, 3, 7], we write:
84 = 2² × 3 × 7
The method in this lesson is trial division: try a candidate divisor, and while it divides the number still remaining, record it and divide.
For the square-root stopping rule and trial-division scope, see Integer factorization.
Factor:
n = 84
Start with two pieces of state:
| State | Value |
|---|---|
remaining | 84 |
factors | [] |
We begin testing candidate divisor d = 2.
Why not test every value up to 84?
If a number has a nontrivial factorization, such as:
a × b = n
then at least one of a or b must be at most sqrt(n).
If both were larger than sqrt(n), their product would be larger than n. Once we have checked all possible divisors through the square root, no unseen smaller factor can remain.
For 84, start with 2:
84 mod 2 = 0, so extract 2.84 / 2 = 42.2 again, because a prime factor can occur more than once.Keep factors in the order in which factors are extracted. Since candidates increase from 2 upward, this gives nondecreasing order.
Trial division in one picture: divide out each candidate while it fits, record it, and stop once d × d exceeds remaining. Whatever is left above 1 is prime. Here 84 = 2² × 3 × 7.
| Step | Candidate d | Check or action | remaining | factors |
|---|---|---|---|---|
| Start | — | Initialize | 84 | [] |
| 1 | 2 | 2 divides 84; record 2, divide | 42 | [2] |
| 2 | 2 | 2 divides 42; record 2, divide | 21 | [2, 2] |
| 3 | 2 | 2 does not divide 21; advance candidate | 21 | [2, 2] |
| 4 | 3 | 3 divides 21; record 3, divide | 7 | [2, 2, 3] |
| 5 | 3 | Check loop boundary: 3 × 3 > 7 | 7 | [2, 2, 3] |
| 6 | — | remaining > 1; append residual 7 | 7 | [2, 2, 3, 7] |
Express repeated factors as a power:
84 = 2² × 3 × 7
Check the result by multiplying the factors:
2 × 2 × 3 × 7 = 84
The final 7 was not found by dividing with candidate 7. We stop earlier because 3 × 3 > 7. At that point, if 7 were composite, it would need a divisor at most sqrt(7), but all relevant smaller candidates have already been processed. Therefore the residual 7 is prime.
After each change above, the following relationship holds:
original_n = product(factors already recorded) × remaining
For the example:
84 = 1 × 8484 = 2 × 4284 = 2 × 2 × 213: 84 = 2 × 2 × 3 × 7Also, every value already recorded in factors is prime.
The loop invariant is:
At every step,
original_n = product(factors already recorded) × remaining, and every recorded factor is prime.
The product relationship says that division never loses part of the original number. We move a factor from remaining into factors.
Why is a recorded divisor prime? Candidates are considered in increasing order. Before we reach a candidate d, all smaller candidates have already been processed completely. If d were composite, it would have a smaller prime factor. That smaller factor would already have been removed from remaining, so composite d cannot still divide remaining.
For a positive integer n:
n < 2, it is not prime.d = 2.d × d <= n:
d divides n, then n is composite.d.n is prime.The inclusive condition matters:
d × d <= n
For 49, candidate 7 must be tested because:
7 × 7 = 49
For integer n >= 2:
remaining = n.d = 2.d × d <= remaining:
d divides remaining:
d;remaining by d.d.remaining > 1, append it as the final prime factor.The inner while is necessary. For 84, 2 divides twice. For 64, it divides six times.
The loop condition uses the changing remaining, not the original input. Every successful division makes remaining smaller, which may let us stop earlier.
isPrimeInput: positive integer n
Return value: true if n is prime; otherwise false
Mutation behavior: does not modify n
Boundary behavior: returns false for n = 1; this lesson’s definition has no prime below 2
1function isPrime(n):
2 # Input: positive integer n
3 # Returns: true exactly when n is prime
4 # Mutation: none
5
6 if n < 2:
7 return false
8
9 d = 2
10
11 while d * d <= n:
12 if n mod d == 0:
13 return false
14 d = d + 1
15
16 return truefactorizeInput: integer n >= 2
Return value: a list of the prime factors of n, in nondecreasing order
Mutation behavior: does not modify input n; modifies only local remaining and the newly created output list
Boundary behavior: this contract excludes n = 1, because 1 has no prime-factor product
1function factorize(n):
2 # Input: integer n >= 2
3 # Returns: prime factors of n in nondecreasing order
4 # Mutation: n is unchanged; only local state and returned list change
5
6 original_n = n
7 remaining = n
8 factors = empty list
9 d = 2
10
11 while d * d <= remaining:
12 while remaining mod d == 0:
13 append d to factors
14 remaining = remaining / d
15
16 d = d + 1
17
18 if remaining > 1:
19 append remaining to factors
20
21 return factorsoriginal_n is included to name the original input used by the invariant and by a later verification:
product(factors) = original_n
Run factorize(84) line by line.
| Pseudocode action | original_n | remaining | d | factors |
|---|---|---|---|---|
original_n = n | 84 | — | — | — |
remaining = n | 84 | 84 | — | — |
factors = empty list | 84 | 84 | — | [] |
d = 2 | 84 | 84 | 2 | [] |
Check 2 × 2 <= 84 | 84 | 84 | 2 | [] |
Check 84 mod 2 == 0 | 84 | 84 | 2 | [] |
append 2; remaining = 84 / 2 | 84 | 42 | 2 | [2] |
Check 42 mod 2 == 0 | 84 | 42 | 2 | [2] |
append 2; remaining = 42 / 2 | 84 | 21 | 2 | [2, 2] |
Check 21 mod 2 == 0 | 84 | 21 | 2 | [2, 2] |
Inner loop ends; d = d + 1 | 84 | 21 | 3 | [2, 2] |
Check 3 × 3 <= 21 | 84 | 21 | 3 | [2, 2] |
Check 21 mod 3 == 0 | 84 | 21 | 3 | [2, 2] |
append 3; remaining = 21 / 3 | 84 | 7 | 3 | [2, 2, 3] |
Check 7 mod 3 == 0 | 84 | 7 | 3 | [2, 2, 3] |
Inner loop ends; d = d + 1 | 84 | 7 | 4 | [2, 2, 3] |
Check 4 × 4 <= 7 | 84 | 7 | 4 | [2, 2, 3] |
Outer loop ends; check remaining > 1 | 84 | 7 | 4 | [2, 2, 3] |
Append residual 7 | 84 | 7 | 4 | [2, 2, 3, 7] |
return factors | 84 | 7 | 4 | [2, 2, 3, 7] |
The return value is:
[2, 2, 3, 7]
Its product is:
2 × 2 × 3 × 7 = 84
First consider n < 2.
A prime must be greater than 1, so no integer less than 2 is prime. Returning false is correct.
Now consider n >= 2.
If the algorithm finds a divisor d with:
2 <= d and d × d <= n
then d divides n, and d is neither 1 nor n. Therefore n has a nontrivial divisor and is composite.
If the algorithm finishes without finding such a divisor, suppose for contradiction that n were composite. Then:
n = a × b
for positive integers a and b with both greater than 1. At least one factor must be at most sqrt(n). The algorithm checks every integer candidate from 2 through that boundary, so it would have found a divisor. This contradicts the assumption that the loop finished without one. Therefore n is prime.
Use the stated invariant:
original_n = product(factors) × remaining
and every recorded factor is prime.
Before either loop runs:
factors is empty, whose product is treated as 1.remaining = original_n.So:
original_n = 1 × remaining
No factors have been recorded, so the claim that every recorded factor is prime is also true.
Suppose the invariant is true before one successful inner-loop iteration.
The algorithm finds that d divides remaining. It appends d and replaces:
remaining with remaining / d
The recorded-factor product gains a factor of d, while remaining loses that same factor. Their total product stays unchanged:
product(old factors) × old remaining
= product(old factors) × d × (old remaining / d)
= product(new factors) × new remaining
Also, d is prime. All smaller candidates have already been processed completely. If d were composite, it would contain a smaller prime divisor that would already have been removed from remaining. Thus appending d preserves the condition that recorded factors are prime.
Repeated division continues until d no longer divides remaining. Every occurrence of that prime factor is recorded.
Increasing d does not change factors or remaining, so it also preserves the invariant.
The outer loop ends when:
d × d > remaining
If remaining = 1, every part of the original number is already represented in factors.
If remaining > 1, it must be prime. If it were composite, it would have a divisor at most sqrt(remaining). The algorithm has already processed every candidate below d, and d × d > remaining means no unprocessed candidate can be at or below that square root. This is impossible for a composite number.
Appending a residual remaining > 1 adds one final prime factor.
The invariant then gives:
original_n = product(returned factors)
and every returned value is prime. Therefore factorize returns a valid prime factorization.
The primality test tries:
d = 2, 3, 4, ...
while:
d × d <= n
The largest possible tested candidate is at most floor(sqrt(n)).
There are at most:
floor(sqrt(n)) - 1
candidate values from 2 through floor(sqrt(n)).
Under the course integer-operation model, each divisibility check:
n mod d == 0
takes constant time.
The work is proportional to the number of candidates checked:
O(sqrt(n)) time.
The algorithm stores only d and the input value. It uses:
O(1) auxiliary space.
Factorization also advances d only while:
d × d <= remaining
The value of remaining can only decrease after successful divisions. Thus the candidate divisor rises only through the square root of the changing remaining value.
There are at most floor(sqrt(n)) - 1 candidate values to consider relative to the original input bound. Successful divisions reduce remaining; they do not create additional larger candidate values to test. Therefore trial-division factorization takes:
O(sqrt(n)) time under the same integer-operation model.
If the returned list contains k factors, storing that list uses:
O(k) output space.
Excluding the returned list, the local variables original_n, remaining, and d use:
O(1) auxiliary space.
Incorrect assumption: 1 is prime.
Exposing input: n = 1
Wrong result: report prime
Why it fails: the definition requires a prime to be greater than 1.
Correction:
1if n < 2:
2 return falseFor factorization, 1 has no prime-factor product, so it is outside the factorize(n) contract used here.
Incorrect loop condition:
1while d * d < n:Exposing input: n = 49
Wrong result: report prime
Wrong state: when d = 7, 7 × 7 < 49 is false, so the algorithm never tests 49 mod 7.
Correction:
1while d * d <= n:The equality case is required because a square can have its nontrivial divisor exactly at its square root.
Incorrect factorization step:
1if remaining mod d == 0:
2 append d to factors
3 remaining = remaining / dExposing input: n = 72
Wrong result: [2, 3] or another incomplete decomposition.
Wrong state: after extracting one 2, remaining is still divisible by 2. A single if moves on before recording all copies.
Correction:
1while remaining mod d == 0:
2 append d to factors
3 remaining = remaining / dThe loop continues until the candidate no longer divides the remaining value.
Incorrect ending: return factors immediately after the outer loop.
Exposing input: n = 14
Wrong result: [2]
Wrong state: after extracting 2, remaining = 7. The loop stops because 3 × 3 > 7, but 7 has not yet been recorded.
Correction:
1if remaining > 1:
2 append remaining to factors| Input | Correct classification or factorization |
|---|---|
1 | neither prime nor composite; no prime-factor product |
2 | prime; [2] |
49 | composite; [7, 7] |
97 | prime; factorization retains residual [97] |
64 | [2, 2, 2, 2, 2, 2] |
Implement factorize(n) for integer n >= 2.
Required return value: prime factors in nondecreasing order.
Executable test contract:
n.1def is_prime(n):
2 if n < 2:
3 return False
4 d = 2
5 while d * d <= n: # <= so that 49 tests d = 7
6 if n % d == 0:
7 return False
8 d += 1
9 return True
10
11def factorize(n):
12 remaining, factors, d = n, [], 2
13 while d * d <= remaining:
14 while remaining % d == 0: # a prime can divide more than once
15 factors.append(d)
16 remaining //= d
17 d += 1
18 if remaining > 1:
19 factors.append(remaining) # the residual is prime
20 return factors
21
22print("factorize(84) =", factorize(84))
23print("isPrime(49) =", str(is_prime(49)).lower())
24print("isPrime(97) =", str(is_prime(97)).lower())
25print("factorize(97) =", factorize(97))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static boolean isPrime(int n) {
6 if (n < 2) return false;
7 for (int d = 2; d * d <= n; d++) { // <= so that 49 tests d = 7
8 if (n % d == 0) return false;
9 }
10 return true;
11 }
12
13 static List<Integer> factorize(int n) {
14 int remaining = n;
15 List<Integer> factors = new ArrayList<>();
16 for (int d = 2; d * d <= remaining; d++) {
17 while (remaining % d == 0) { // a prime can divide more than once
18 factors.add(d);
19 remaining /= d;
20 }
21 }
22 if (remaining > 1) factors.add(remaining); // the residual is prime
23 return factors;
24 }
25
26 public static void main(String[] args) {
27 System.out.println("factorize(84) = " + factorize(84));
28 System.out.println("isPrime(49) = " + isPrime(49));
29 System.out.println("isPrime(97) = " + isPrime(97));
30 System.out.println("factorize(97) = " + factorize(97));
31 }
32}1#include <iostream>
2#include <vector>
3using namespace std;
4
5bool isPrime(int n) {
6 if (n < 2) return false;
7 for (int d = 2; d * d <= n; d++) { // <= so that 49 tests d = 7
8 if (n % d == 0) return false;
9 }
10 return true;
11}
12
13vector<int> factorize(int n) {
14 int remaining = n;
15 vector<int> factors;
16 for (int d = 2; d * d <= remaining; d++) {
17 while (remaining % d == 0) { // a prime can divide more than once
18 factors.push_back(d);
19 remaining /= d;
20 }
21 }
22 if (remaining > 1) factors.push_back(remaining); // the residual is prime
23 return factors;
24}
25
26void show(const char* label, const vector<int>& v) {
27 cout << label << "[";
28 for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
29 cout << "]" << endl;
30}
31
32int main() {
33 show("factorize(84) = ", factorize(84));
34 cout << boolalpha << "isPrime(49) = " << isPrime(49) << endl;
35 cout << "isPrime(97) = " << isPrime(97) << endl;
36 show("factorize(97) = ", factorize(97));
37}1function isPrime(n) {
2 if (n < 2) return false;
3 for (let d = 2; d * d <= n; d++) { // <= so that 49 tests d = 7
4 if (n % d === 0) return false;
5 }
6 return true;
7}
8
9function factorize(n) {
10 let remaining = n;
11 const factors = [];
12 for (let d = 2; d * d <= remaining; d++) {
13 while (remaining % d === 0) { // a prime can divide more than once
14 factors.push(d);
15 remaining /= d;
16 }
17 }
18 if (remaining > 1) factors.push(remaining); // the residual is prime
19 return factors;
20}
21
22const show = (a) => `[${a.join(', ')}]`;
23console.log("factorize(84) = " + show(factorize(84)));
24console.log("isPrime(49) = " + isPrime(49));
25console.log("isPrime(97) = " + isPrime(97));
26console.log("factorize(97) = " + show(factorize(97)));Return false for n below 2, then test every d from 2 while d × d <= n. If none divides n, it is prime. The test must use <=, otherwise 49 passes as prime.
If n = a × b with both factors above sqrt(n), the product would exceed n. So a composite number always has a divisor at most sqrt(n). Once d × d > remaining, no unchecked divisor is left.
84 = 2² × 3 × 7. The algorithm records 2 twice, then 3, and the leftover 7 is appended at the end because 3 × 3 > 7.
A prime can divide the number more than once. With a single if, 72 would lose copies of 2 and give an incomplete result. The while loop divides out every copy before moving to the next d.
The loop can stop while remaining is a prime larger than every candidate tried. For 14, after dividing out 2 the value 7 remains and 3 × 3 > 7, so 7 is recorded last. Without that step you would return [2].
Trial division factors or tests one number in O(sqrt(n)). The sieve crosses out multiples to list every prime up to n in one pass. Use trial division for a single number, the sieve for many.