Trial Division Factorization

Trial division is the most straightforward method for prime factorization. It works by systematically testing whether a number is divisible by smaller numbers, starting from 2 and continuing up to the square root of the number being factored. While simple to understand and implement, its time complexity makes it inefficient for large numbers.

Algorithm Overview

The trial division algorithm operates by dividing the input number by each potential factor, starting from 2. When a factor is found, it is added to the list of prime factors, and the process continues with the quotient. The algorithm stops when the remaining number becomes 1 or when we've tested all possible factors up to the square root of the original number.

Time and Space Complexity

The time complexity of trial division is , where n is the number being factored. This is because we only need to check potential factors up to the square root of n. The space complexity is to store the prime factors.

JavaScript Implementation

code.js
1function trialDivision(n) {
2    const factors = [];
3    
4    // Handle 2 separately
5    while (n % 2 === 0) {
6        factors.push(2);
7        n = n / 2;
8    }
9    
10    // Check odd numbers up to sqrt(n)
11    for (let i = 3; i <= Math.sqrt(n); i += 2) {
12        while (n % i === 0) {
13            factors.push(i);
14            n = n / i;
15        }
16    }
17    
18    // If n is still greater than 2, it's a prime factor
19    if (n > 2) {
20        factors.push(n);
21    }
22    
23    return factors;
24}

Example Usage

Let's factorize the number 84:

code.js
1const result = trialDivision(84);
2console.log(result); // [2, 2, 3, 7]

This means that 84 = 2 × 2 × 3 × 7.

Optimization Techniques

While the basic implementation is straightforward, several optimizations can improve its performance:

1. Pre-computing small primes using the Sieve of Eratosthenes
2. Using wheel factorization to skip numbers that are known to be composite
3. Implementing early termination when the remaining number is prime

Limitations

The main limitation of trial division is its poor performance on large numbers. For numbers with large prime factors, the algorithm must test many potential divisors, making it impractical for cryptographic applications or factoring very large numbers.

Applications

Despite its limitations, trial division remains useful for:

• Educational purposes to understand prime factorization
• Factoring small numbers (up to 10-12 digits)
• As a component in more sophisticated factorization algorithms
• Quick checks for small prime factors in composite numbers