Efficient Prime Factorization

The Fundamental Theorem of Arithmetic

At the heart of today's topic is a concept you may already know: the Fundamental Theorem of Arithmetic. It states that every integer greater than 1 is either a prime number itself or can be represented as a unique product of prime numbers.

For example:

• 60 = 2 * 2 * 3 * 5
• 99 = 3 * 3 * 11
• 7 is just 7 (it's already prime)

Our goal is to write a program that takes an integer n and outputs this list of prime factors.

From a Naive Approach to an Efficient One

How might we start? A very basic idea would be to iterate a number i from 2 up to n. If i divides n, we've found a factor. Since we are checking in increasing order, the first factor we find must be prime. We can then repeatedly divide n by i to remove all occurrences of that factor.

This approach, however, can be very slow. Consider what happens if the input n is a large prime number. The loop would have to run all the way up to n, leading to an O(n) complexity, which is too slow for competitive programming constraints.

To understand this bottleneck and the need for optimization, the following video provides a clear explanation.

The O(sqrt(n)) Optimization

Fortunately, we can do much better. The key insight is the same one we used for the O(sqrt(n)) primality test:

If a composite number n has a prime factor, it must have at least one prime factor less than or equal to sqrt(n).

This means we don't need to check for factors all the way up to n. We can stop our search at sqrt(n). This dramatically reduces our search space and is the core of the efficient algorithm.

But this raises a question: What about prime factors that are larger than sqrt(n)?

Let's think about it. An integer n can have at most one prime factor greater than sqrt(n). Why? If it had two such factors, say p1 and p2 where p1 > sqrt(n) and p2 > sqrt(n), then their product p1 * p2 would be greater than sqrt(n) * sqrt(n) = n. This is a contradiction.

So, our strategy is:

1. Find and divide out all prime factors up to sqrt(n).
2. After this process, if the remaining value of n is greater than 1, it must be that single, large prime factor.

For a clear explanation of this logic, we can continue with the CodeNCode video.

The Algorithm in C++

Let's translate this logic into a clean C++ implementation. The cp-algorithms website, an essential resource for competitive programmers, provides a canonical implementation.

Let's break down that trial_division1 code:

vector<long long> trial_division1(long long n) {
    vector<long long> factorization;
    // 1. Loop for potential divisors up to sqrt(n)
    for (long long d = 2; d * d <= n; d++) {
        // 2. If d is a divisor, extract all powers of it
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    // 3. Handle the case of a large prime factor
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

1. The for loop iterates through potential divisors d from 2 up to sqrt(n). The condition d * d <= n is a common and safe way to check d <= sqrt(n) while avoiding floating-point arithmetic and potential precision issues.
2. The while loop is crucial. If d divides n, it adds d to the factors list and then divides n by d. It repeats this until n is no longer divisible by d. This ensures we extract all occurrences of a prime factor (e.g., all three 2s from 24).
3. The final if (n > 1) is the elegant part that handles the case we discussed earlier. If n has been fully factored by primes less than or equal to its original square root, the remaining n will be 1. If there was a prime factor greater than the original sqrt(n) (e.g., the factor 13 in n=26), it will be the value of n that remains at the end.

A Small Optimization: Wheel Factorization

We can make a small but effective improvement. Once we check for the factor 2, we know that no other even number can be a prime factor. We can then start our loop at 3 and increment by 2, checking only odd numbers. This cuts the number of iterations in the main loop by half.

This idea is a simplified version of "Wheel Factorization". The GeeksforGeeks article below provides an implementation that shows this exact optimization.

Putting It All Together: Sieve and Factorization

We can connect today's lesson with our previous one on the Sieve of Eratosthenes. If a problem requires you to factorize many numbers within a certain range (e.g., up to 10^6), you can gain a significant speedup.

1. Pre-computation: Run the Sieve of Eratosthenes to generate all prime numbers up to sqrt(N_max), where N_max is the maximum value of n you need to factor.
2. Factorization: In your factorization function, instead of iterating d = 2, 3, 4, 5, ..., iterate only through the list of pre-computed primes.

This avoids checking composite numbers like 4, 6, 8, etc., as potential divisors, making your factorization loop even faster. The cp-algorithms article briefly describes this powerful combination.

This technique is a perfect example of the pre-computation mindset that is essential for success in competitive programming.

Key Takeaways

• The prime factorization of a number is its unique representation as a product of primes.
• A naive O(n) approach is too slow for large inputs.
• The efficient O(sqrt(n)) algorithm relies on the fact that any composite number n has a prime factor less than or equal to sqrt(n).
• The algorithm's key steps are:
  1. Iterate through potential divisors d up to sqrt(n).
  2. For each d, use a while loop to divide n by d repeatedly until it's no longer divisible.
  3. After the loop, if n is still greater than 1, this remaining n is the last prime factor.
• This method can be further optimized by handling 2 separately and only checking odd divisors, or by using a pre-computed list of primes from a sieve.

We have now covered primality testing, generating primes with a sieve, and prime factorization. These are the absolute fundamentals of number theory for competitive programming. In our next lesson, we will shift gears to explore the relationship between two numbers by learning the Euclidean algorithm to find their Greatest Common Divisor (GCD).