Trial Division

Trial division is the most straightforward method for determining whether a number is prime. While not the most efficient for large numbers, it serves as a foundational concept in prime testing and is perfectly suitable for small numbers.

Mathematical Definition

A number n is prime if and only if it has exactly two factors: 1 and itself. Trial division works by checking if any number from 2 to divides n evenly. If no such divisor is found, then n is prime.

The mathematical foundation is based on the following theorem:

If n is composite, then n has a prime factor less than or equal to .

This is because if n = ab where a and b are integers greater than 1, then either:

• a ≤ or
• b ≤

Time and Space Complexity

The time complexity of trial division is:

where n is the number being tested. This makes it impractical for very large numbers, but efficient for small numbers.

The space complexity is:

as we only need a constant amount of memory regardless of input size.

JavaScript Implementation

Here's a basic implementation of trial division:

code.js
1function isPrime(n) {
2    // Handle edge cases
3    if (n <= 1) return false;
4    if (n <= 3) return true;
5    if (n % 2 === 0 || n % 3 === 0) return false;
6    
7    // Check all numbers of form 6k ± 1 up to sqrt(n)
8    for (let i = 5; i * i <= n; i += 6) {
9        if (n % i === 0 || n % (i + 2) === 0) {
10            return false;
11        }
12    }
13    
14    return true;
15}
16
17// Example usage:
18console.log(isPrime(17));  // true
19console.log(isPrime(24));  // false

Optimizations

Several optimizations can be applied to the basic trial division algorithm:

1. Skip Even Numbers: After checking 2, we can skip all even numbers since they can't be prime.
2. Skip Multiples of 3: After checking 3, we can skip all multiples of 3.
3. Wheel Factorization: We can extend this pattern to create a "wheel" that skips numbers that are definitely not prime.

Here's an optimized version using wheel factorization:

code.js
1function isPrimeOptimized(n) {
2    // Handle small numbers and obvious non-primes
3    if (n <= 1) return false;
4    if (n <= 3) return true;
5    if (n % 2 === 0 || n % 3 === 0) return false;
6    
7    // Create a wheel of increments that skips multiples of 2 and 3
8    const wheel = [4, 2, 4, 2, 4, 6, 2, 6];
9    let wheelIndex = 0;
10    let i = 5;
11    
12    while (i * i <= n) {
13        if (n % i === 0) return false;
14        i += wheel[wheelIndex];
15        wheelIndex = (wheelIndex + 1) % 8;
16    }
17    
18    return true;
19}

Finding Prime Factors

Trial division can also be used to find all prime factors of a number:

code.js
1function primeFactors(n) {
2    const factors = [];
3    
4    // Handle factors of 2
5    while (n % 2 === 0) {
6        factors.push(2);
7        n = n / 2;
8    }
9    
10    // Handle odd factors
11    for (let i = 3; i * i <= 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 prime
19    if (n > 2) {
20        factors.push(n);
21    }
22    
23    return factors;
24}
25
26// Example usage:
27console.log(primeFactors(84));  // [2, 2, 3, 7]

Applications

Trial division is useful in several contexts:

1. Educational purposes - it's the most intuitive way to understand primality testing
2. Testing small numbers (roughly up to 10⁶)
3. Finding all prime factors of a number
4. Verification of results from probabilistic primality tests

Limitations

The main limitations of trial division are:

1. Poor performance for large numbers
2. Not suitable for cryptographic applications
3. Inefficient for numbers with large prime factors

For testing large numbers, more sophisticated algorithms like Miller-Rabin or AKS are recommended.