Understanding Prime Factorization Algorithms: Theory and Code

1. Introduction and Core Concepts

Prime factorization algorithms are a fundamental class of mathematical algorithms that decompose a composite integer into its prime constituents. Every integer greater than 1 can be represented uniquely as a product of prime numbers, a principle known as the Fundamental Theorem of Arithmetic. For example, 60 = 2 × 2 × 3 × 5, and 84 = 2 × 2 × 3 × 7. Prime factorization algorithms provide systematic methods to compute this decomposition efficiently, and they form the backbone of modern number theory, cryptography, and computational mathematics.

Understanding prime factorization algorithms matters far beyond pure mathematics. While the concept appears elementary, the computational difficulty of factoring large integers is what secures much of the modern internet. The RSA cryptosystem, which protects online banking, e-commerce, and private communications, relies directly on the assumption that factoring a 2048-bit semiprime (a product of two large primes) is infeasible with current algorithms and hardware. Consequently, advances in prime factorization algorithms have profound implications for cybersecurity, and studying them helps engineers appreciate both the power and the limits of computation.

At its core, a prime factorization algorithm takes an integer n and returns a multiset of primes whose product equals n. The output is often represented as a dictionary of prime to exponent, such as 360 = 2^3 × 3^2 × 5^1. Key concepts that underpin all prime factorization algorithms include divisibility, primality testing, trial division, and the use of greatest common divisor (GCD) computations. An efficient algorithm must balance two competing goals: correctness across all inputs and performance on large inputs where naive methods become prohibitively slow. The choice of algorithm depends heavily on the size and structure of the number being factored.

Why Prime Factorization Is Computationally Unique

Unlike sorting or searching, where polynomial-time solutions are well established, no known algorithm can factor arbitrary large integers in polynomial time on a classical computer. The best known classical algorithms run in sub-exponential time, which means their runtime grows faster than any polynomial but slower than a pure exponential function. This intermediate complexity class makes prime factorization algorithms a central subject in complexity theory and a benchmark for quantum computing, where Shor's algorithm promises exponential speedup.

For practitioners, this means that prime factorization algorithms must be selected contextually. Factoring a 32-bit integer for a programming challenge is trivial with trial division, while factoring a 100-digit number for cryptographic analysis requires sophisticated methods like Pollard's Rho, the Quadratic Sieve, or the General Number Field Sieve. Understanding the spectrum of available techniques allows developers to choose the right tool for the job and to avoid catastrophic performance pitfalls in production systems.

2. How It Works

The most intuitive family of prime factorization algorithms is based on trial division. The theory is straightforward: if n is composite, it must have a divisor d such that 2 <= d <= sqrt(n). By systematically testing divisibility by increasing integers, we can extract prime factors one by one. The algorithm starts by dividing out all factors of 2, then tests odd numbers 3, 5, 7, and so on. Whenever a divisor is found, it is recorded and the number is reduced. The process continues until the remaining value is 1 or is itself prime. This guarantees that only prime factors are collected, because any composite divisor would have already been broken into its prime components earlier.

More advanced prime factorization algorithms exploit mathematical properties to skip unnecessary tests or to find factors faster. For instance, all primes greater than 3 can be expressed in the form 6k ± 1. This observation allows an optimized trial division to test only numbers congruent to 1 or 5 modulo 6, cutting the number of divisions by roughly two-thirds. Other algorithms use entirely different principles. Pollard's Rho algorithm, for example, uses a pseudo-random sequence and Floyd's cycle detection to find a non-trivial divisor via GCD computations. It is based on the birthday paradox: a random sequence modulo n will eventually repeat modulo an unknown factor p of n much sooner than modulo n itself.

Fermat's factorization method approaches the problem from the opposite direction. It expresses an odd integer n as the difference of two squares: n = a^2 - b^2 = (a - b)(a + b). If n has factors close to sqrt(n), this method is extremely efficient. Sieve-based methods like the Quadratic Sieve and General Number Field Sieve extend this idea by searching for many relations of the form x^2 ≡ y^2 (mod n) and combining them using linear algebra over GF(2) to produce a factorization. These methods do not test divisors sequentially but instead collect smooth numbers and solve a system of equations, which is why they excel on very large inputs.

The Role of Primality Testing

Almost every modern prime factorization algorithm relies on a fast primality test to avoid wasted effort. Before attempting to factor a number, the algorithm checks whether it is already prime using a probabilistic test like Miller-Rabin or a deterministic test for smaller ranges. If the number is prime, the recursion terminates immediately. This interleaving of primality testing and factoring is crucial for recursive algorithms like Pollard's Rho, where the number is repeatedly split into smaller factors until all pieces are proven prime. Without this check, the algorithm would continue trying to factor primes indefinitely.

Another core mechanism is the use of the greatest common divisor. Many advanced algorithms do not directly find a divisor by trial but instead compute gcd(|x - y|, n) for carefully chosen x and y. If x ≡ y (mod p) for some unknown prime factor p of n, but x ≠ y (mod n), then gcd(|x - y|, n) will reveal p. This indirect approach is powerful because it can discover a factor without ever guessing it explicitly, which is the key insight that makes Pollard's Rho and related methods sub-exponential in practice.

3. Implementation

Implementing prime factorization algorithms in Python requires attention to integer arithmetic, loop bounds, and edge cases. The simplest implementation, trial division, is easy to write, easy to verify, and sufficient for numbers up to 10^12. The optimized versions introduce small but important improvements that dramatically reduce runtime for moderately large inputs. Below are four representative implementations that cover the spectrum from educational to production-ready for different constraints.

The first implementation is the classic trial division algorithm. It handles the factor 2 separately to allow incrementing by 2 thereafter, which halves the number of iterations. The loop condition f * f <= n ensures we only test divisors up to the square root of the current value of n, which shrinks as factors are removed. This dynamic bound is a critical optimization often missed by beginners who compute sqrt(n) once at the beginning.

import math

def prime_factors_trial_division(n: int) -> list[int]:
    """Return prime factors of n with multiplicity using trial division."""
    if n < 2:
        return []
    factors = []
    # Extract all factors of 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # Test odd divisors starting from 3
    f = 3
    while f * f <= n:
        while n % f == 0:
            factors.append(f)
            n //= f
        f += 2
    # If remainder is prime greater than 2
    if n > 1:
        factors.append(n)
    return factors

# Example: prime_factors_trial_division(360) -> [2, 2, 2, 3, 3, 5]

The second implementation uses the 6k ± 1 optimization. After removing factors of 2 and 3, every remaining prime must be of the form 6k - 1 or 6k + 1. By alternating steps of 2 and 4, we generate the sequence 5, 7, 11, 13, 17, 19, 23, 25... and skip numbers divisible by 2 or 3. This reduces the number of trial divisions by about 66% compared to testing all odd numbers, with negligible additional code complexity. For numbers up to 10^12, this optimization can cut runtime by more than half.

import math

def prime_factors_optimized(n: int) -> list[int]:
    """Optimized trial division using 6k ± 1 wheel."""
    if n < 2:
        return []
    factors = []
    # Remove factors of 2 and 3
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    while n % 3 == 0:
        factors.append(3)
        n //= 3
    # Check divisors of form 6k ± 1
    i = 5
    step = 2  # alternates 2, 4 to generate 5,7,11,13...
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += step
        step = 6 - step
    if n > 1:
        factors.append(n)
    return factors

# Example: prime_factors_optimized(1001) -> [7, 11, 13]

For larger integers where trial division becomes too slow, Pollard's Rho provides a probabilistic alternative with much better expected performance. The following implementation combines Pollard's Rho for finding a non-trivial divisor with Miller-Rabin for primality testing and recursion to fully factor the number. This hybrid approach is the standard technique used in competitive programming and cryptographic libraries for factoring 64-bit integers quickly.

import math
import random

def is_probable_prime(n: int, k: int = 7) -> bool:
    """Miller-Rabin primality test (deterministic for n < 2^64 with correct bases)."""
    if n < 2:
        return False
    # Small primes
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for p in small_primes:
        if n % p == 0:
            return n == p
    # Write n-1 as d * 2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def pollard_rho(n: int) -> int:
    """Return a non-trivial divisor of composite n."""
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    while True:
        c = random.randrange(1, n)
        f = lambda x: (pow(x, 2, n) + c) % n
        x = random.randrange(2, n)
        y = x
        d = 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x - y), n)
        if d != n:
            return d

def factor_pollard_rho(n: int, res: list[int]):
    """Recursively factor n and append prime factors to res."""
    if n == 1:
        return
    if is_probable_prime(n):
        res.append(n)
    else:
        d = pollard_rho(n)
        factor_pollard_rho(d, res)
        factor_pollard_rho(n // d, res)

When many queries must be answered for numbers up to a fixed limit, precomputing the smallest prime factor (SPF) with a sieve is optimal. The sieve runs once in O(n log log n) time and then each factorization is reduced to repeated division by the SPF, which takes O(log n) time per query. This technique is invaluable for problems that require factoring thousands or millions of numbers, such as computing divisor functions or building prime factor histograms.

def sieve_smallest_prime_factor(limit: int) -> list[int]:
    """Precompute smallest prime factor for every number up to limit."""
    spf = list(range(limit + 1))
    spf[0] = 0
    spf[1] = 1
    # Sieve: for each prime i, mark its multiples
    for i in range(2, int(limit**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, limit + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def factor_with_spf(n: int, spf: list[int]) -> list[int]:
    """Factor n in O(log n) using precomputed spf table."""
    if n < 2:
        return []
    factors = []
    while n > 1:
        p = spf[n]
        factors.append(p)
        n //= p
    return factors

# Usage for bulk queries:
# spf = sieve_smallest_prime_factor(10**6)
# print(factor_with_spf(123456, spf))  # -> [2, 2, 2, 2, 2, 2, 3, 643]
# print(factor_with_spf(999983, spf))  # -> [999983] (prime)

4. Step-by-Step Example

To make the mechanics of prime factorization algorithms concrete, let us walk through the optimized trial division algorithm factoring n = 84, then a larger example n = 9973 × 9967 to illustrate when trial division struggles and Pollard's Rho excels. Tracing the algorithm step by step reveals why the loop bound shrinks and how composite divisors are never mistakenly recorded as prime factors.

We begin with n = 84. The algorithm first removes factors of 2. Since 84 % 2 == 0, we append 2 and set n = 42. Again 42 % 2 == 0, so we append another 2 and set n = 21. Now n % 2 != 0, so we move to factors of 3. Since 21 % 3 == 0, we append 3 and set n = 7. Now n % 3 != 0, so we enter the 6k ± 1 loop with i = 5. We check whether i * i <= n, which is 25 <= 7, which is false, so the loop is skipped entirely. Finally, since n > 1 (7 > 1), we append the remaining n = 7. The result is [2, 2, 3, 7], and indeed 2 × 2 × 3 × 7 = 84.

Notice how the algorithm guarantees primality of the factors without an explicit primality test. When we tested divisor 4, it was never considered because we had already removed all factors of 2. Similarly, divisor 6 was skipped because it is 6k, not 6k ± 1. Any composite number that survives to be tested would have a prime factor smaller than itself that would have already divided n. This is why trial division, despite its simplicity, correctly returns only primes.

Walkthrough with a Larger Semiprime

Consider n = 99,400,891, which equals 9967 × 9973. Both factors are primes close to 10,000. Optimized trial division will test divisors 5, 7, 11, 13, and so on, all the way up to 9967. That requires testing roughly 3,300 candidates (one third of numbers up to 9967), which is feasible but noticeably slower. Each division is cheap, but the sheer count adds up. For a 12-digit semiprime with factors near 1,000,000, trial division would need to test about 330,000 candidates, which becomes impractical in time-sensitive applications.

Pollard's Rho handles this case differently. It picks a random polynomial f(x) = x^2 + c mod n and generates sequences x, y = f(f(y)). It computes d = gcd(|x - y|, n) at each step. Because the sequences behave randomly modulo p = 9967 and modulo q = 9973, the birthday paradox predicts a collision modulo p after about sqrt(p) ≈ 100 steps. When x ≡ y (mod p) but not (mod n), the gcd will be p, revealing the factor without ever testing 9967 directly. In practice, Pollard's Rho factors this 8-digit semiprime in under a millisecond, while trial division might take tens of milliseconds, a gap that widens exponentially as digits increase.

This contrast highlights a key lesson: prime factorization algorithms are not interchangeable. Trial division is deterministic and simple but scales poorly with the size of the smallest prime factor. Pollard's Rho is probabilistic and slightly more complex but scales with the square root of the smallest factor, making it vastly superior for numbers with large prime factors. For numbers with many small factors, like 2^20 × 3^15, trial division is actually faster because it quickly peels off small primes.

5. Complexity Analysis

Complexity analysis of prime factorization algorithms is nuanced because runtime depends not only on n but also on the distribution of its prime factors. The worst case for trial division occurs when n is prime or a product of two large primes of similar size, forcing the algorithm to test all candidates up to sqrt(n). The best case occurs when n is even or has a very small prime factor, allowing early termination. Understanding these distinctions is essential for predicting performance in real workloads.

For trial division, the time complexity is O(sqrt(n)) divisions in the worst case, which is exponential in the number of bits b = log2(n), since sqrt(n) = 2^(b/2). The space complexity is O(1) aside from the output list, or O(log n) if counting the recursion stack for variants that return factor counts. The optimized 6k ± 1 wheel reduces the constant factor by 3 but does not change the asymptotic complexity. Pollard's Rho has an expected time complexity of O(n^(1/4) polylog n) or more precisely O(sqrt(p)) where p is the smallest prime factor, which is still exponential in bits but with a much smaller exponent. Its space complexity is O(1).

Sieve-based methods shift the cost model. Building the smallest prime factor table up to N costs O(N log log N) time and O(N) space, but then each query costs only O(log n) time. This is ideal when N is moderate (e.g., 10^6 or 10^7) and many numbers must be factored. Sub-exponential algorithms like the Quadratic Sieve run in time exp((1 + o(1)) sqrt(ln n ln ln n)), and the General Number Field Sieve runs in exp((c + o(1))(ln n)^(1/3)(ln ln n)^(2/3)), which is the best known for numbers over 100 digits. These complexities are difficult to achieve in pure Python and are typically implemented in C with extensive optimizations.

The table above summarizes the asymptotic behavior, but constant factors and implementation details matter enormously in practice. A well-optimized trial division in PyPy with integer arithmetic may outperform a poorly implemented Pollard's Rho for numbers under 10^12 due to Python's overhead for random number generation and GCD calls. Conversely, for a 60-bit semiprime, Pollard's Rho will be orders of magnitude faster despite its probabilistic nature. When benchmarking prime factorization algorithms, always test on the distribution of inputs you expect in production, not just worst-case primes.

6. Variations and Optimizations

Beyond the basic trial division and Pollard's Rho, several variations and optimizations can significantly improve the practical performance of prime factorization algorithms. These techniques range from simple wheel sieves that skip obvious composites to advanced methods that change the underlying mathematical approach. Choosing the right optimization depends on the constraints of your problem: maximum n, number of queries, available memory, and acceptable error probability.

Wheel factorization generalizes the 6k ± 1 idea. A 30-wheel skips numbers divisible by 2, 3, or 5, testing only 8 out of every 30 numbers (those coprime to 30). A 210-wheel skips multiples of 2, 3, 5, and 7, testing 48 out of 210 numbers. Each larger wheel reduces the number of divisions but increases code complexity and precomputation. In practice, a 30-wheel is often the sweet spot for Python, while larger wheels are more common in C implementations where loop overhead is lower. Another simple optimization is to precompute primes up to sqrt(n) using a sieve and then trial divide only by primes, rather than all odd numbers. This eliminates composite trial divisors entirely but requires O(sqrt(n)) memory for the prime list.

For Pollard's Rho, optimizations include using Brent's cycle detection instead of Floyd's, which reduces GCD computations by accumulating products and computing GCDs in batches. This can double the speed. Choosing the polynomial f(x) = x^2 + c with different c values and using a fast GCD implementation (math.gcd in Python is already implemented in C) also matters. For the Miller-Rabin primality test that accompanies Pollard's Rho, using deterministic bases for 64-bit integers (e.g., [2, 325, 9375, 28178, 450775, 9780504, 1795265022]) makes the test deterministic and avoids the need for many random bases.

Advanced Sieve Methods

When factoring many numbers up to a large limit, segmented sieves and linear sieves offer memory and speed improvements. A segmented sieve factors numbers in intervals, using O(sqrt(N)) memory instead of O(N), which is crucial when N exceeds available RAM. A linear sieve computes smallest prime factors in O(N) time with a slightly more complex inner loop, which can be faster than the classic O(N log log N) sieve for N up to 10^7 in Python when implemented with NumPy or PyPy.

For very large numbers beyond 50 digits, the Quadratic Sieve (QS) and General Number Field Sieve (GNFS) are the state of the art. These algorithms are rarely implemented from scratch in Python for production use; instead, libraries like sympy and sage wrap highly optimized C implementations. However, understanding their existence helps developers know when to delegate to a specialized library rather than attempting to write a custom Pollard's Rho that will never finish on a 100-digit input. A common optimization strategy is to implement a cascade: try trial division for small factors, then Pollard's Rho, then Pollard's p-1, then QS/GNFS, falling through to the next method only if the previous one fails to find a factor within a time budget.

7. Real-World Applications

Prime factorization algorithms are not merely academic exercises; they underpin critical infrastructure across technology, science, and engineering. While cryptography is the most famous application, the same algorithms are used in hash table sizing, random number generation, signal processing, and even in optimizing database query plans. Recognizing these diverse use cases helps engineers appreciate why efficient factorization matters even when they are not building an RSA implementation.

In cryptography, prime factorization algorithms serve both offensive and defensive roles. Defensively, key generation requires generating large random primes and verifying their primality, which relies on factorization-related primality tests. Offensively, cryptanalysts use factorization algorithms to test the strength of keys and to factor weak keys where primes were generated with insufficient entropy. The Logjam and ROCA vulnerabilities, for example, were discovered by analyzing how prime generation and factorization interact in real TLS and smartcard implementations. Outside cryptography, many web servers and load balancers use prime numbers for consistent hashing and for sizing hash tables to reduce collisions, and factorization helps verify that chosen sizes are indeed prime or have desirable factor structures.

In databases and distributed systems, prime factorization supports query optimization and sharding strategies. For instance, when partitioning data across nodes, choosing a number of partitions that is prime or has large prime factors can improve distribution uniformity for certain hash functions. In signal processing, the Fast Fourier Transform (FFT) is most efficient when the transform size has small prime factors; factorization algorithms are used to select optimal FFT sizes or to decompose a large FFT into smaller ones via the Cooley-Tukey algorithm. Compilers and runtime systems also use factorization to unroll loops and vectorize operations when array dimensions have known factor structures.

Even in everyday software development, prime factorization appears in unexpected places. Game engines use it to balance procedural generation, financial systems use it for scheduling periodic tasks with coprime intervals to avoid resonance, and networking stacks use prime-based hashing to distribute packets across queues. The table above illustrates that the choice of prime factorization algorithm is driven by input size and query volume, not just theoretical complexity. A web server sizing a hash table to 10,000 entries has vastly different needs than a security researcher factoring a 768-bit RSA challenge number.

8. Comparison with Alternatives

Prime factorization should not be confused with related but distinct problems: primality testing, prime generation, and divisor enumeration. Primality testing asks only whether a number is prime, without providing factors if it is composite. Prime generation produces new primes of a given size. Divisor enumeration lists all divisors, which requires factorization as a first step but is a more expensive output. Understanding these alternatives helps clarify when factorization is necessary and when a simpler or more specialized algorithm suffices.

Trial division, Pollard's Rho, the Quadratic Sieve, and the General Number Field Sieve represent four points on the spectrum of factorization algorithms. Trial division is deterministic, simple, and fast for small inputs but exponential in the number of bits. Pollard's Rho is probabilistic, moderately complex, and efficient for numbers up to about 60 bits with no single huge prime factor. The Quadratic Sieve is sub-exponential and handles numbers up to about 100 digits, while GNFS is the only practical choice for numbers beyond 100 digits, albeit with enormous implementation complexity. The trade-offs involve not only time but also memory, code size, and the need for high-precision arithmetic.

For many applications, full factorization is overkill. If you only need to know whether a number is prime, Miller-Rabin is exponentially faster than factoring it. If you need to generate a random prime for a hash table, a sieve that produces all primes up to N is more efficient than factoring each candidate. If you need the number of divisors or sum of divisors, you can compute them from the prime factorization, but you do not need to enumerate all divisors explicitly. Choosing the right abstraction level avoids unnecessary computation and simplifies code.

The comparison table makes it clear that there is no single best prime factorization algorithm. For interview problems and most backend services where numbers fit in 64 bits, optimized trial division or Pollard's Rho is the pragmatic choice. For cryptographic research or security audits involving large integers, you should rely on established libraries like sympy.ntheory.factorint, which automatically selects the appropriate method, or call out to specialized tools like msieve or CADO-NFS. Attempting to implement GNFS in pure Python for a production system would be both error-prone and orders of magnitude slower than using a tuned C implementation.

9. Common Mistakes and Best Practices

Even experienced developers make subtle mistakes when implementing prime factorization algorithms, leading to incorrect results, infinite loops, or severe performance degradation. One of the most common errors is using a static loop bound computed once as int(sqrt(n)) at the start, rather than the dynamic condition i * i <= n. As n is divided by small factors, its square root shrinks, and failing to update the bound causes the algorithm to test many unnecessary divisors. Another frequent mistake is forgetting to handle n = 1 or n = 0 as edge cases, or returning an empty list for prime inputs instead of the prime itself.

Integer overflow and floating-point inaccuracies are another pitfall, especially in languages other than Python. Computing sqrt(n) with floating-point arithmetic can produce rounding errors for large n, causing the loop to terminate one iteration too early and miss a factor. In Python, using math.isqrt(n) for integer square root or the condition i * i <= n avoids this entirely. Additionally, using n % i == 0 with i as a float after sqrt conversion will fail silently. Always keep trial divisors as integers and use integer arithmetic for bounds.

Performance pitfalls include testing even numbers after handling factor 2, not skipping multiples of 3, and performing expensive primality tests too frequently. A best practice is to structure the code as a cascade: first peel off small primes with trial division up to a bound like 100 or 1000, then switch to Pollard's Rho for the remaining cofactor. This hybrid approach captures the best of both worlds: fast removal of small factors and efficient handling of large prime factors. Also, when implementing Pollard's Rho, failing to randomize the constant c or the starting values can cause the algorithm to loop forever on certain inputs; always include a retry mechanism with new random parameters if gcd returns n.

Best Practices Checklist

• Always handle edge cases: n < 2, n even, and n prime. Return early when possible.
• Use integer arithmetic for loop bounds: while i * i <= n or for i in range(3, math.isqrt(n)+1, 2).
• Remove small factors first (2, 3, 5) before entering the main loop to reduce iterations.
• Combine trial division with Miller-Rabin and Pollard's Rho for numbers beyond 10^12.
• For many queries up to N, precompute smallest prime factors once with a sieve and reuse the table.
• Test with known values: primes, prime powers (e.g., 2^20), semiprimes, and Carmichael numbers.
• Avoid floating-point sqrt for bounds; use math.isqrt in Python 3.8+ for exact integer sqrt.
• When using Pollard's Rho, implement Brent's optimization and batch GCDs for speed.

Finally, remember that correctness is more important than micro-optimizations. A simple, correct trial division that passes all tests is preferable to a complex, buggy Quadratic Sieve that fails on edge cases. Write clear, commented code, include assertions for invariants like product(factors) == original_n, and benchmark on realistic data before optimizing. In production systems that factor numbers for security purposes, always use well-tested libraries rather than custom implementations, and keep dependencies updated to benefit from the latest algorithmic improvements.

10. Interview Questions

Prime factorization algorithms are a staple of technical interviews because they test number theory, loop invariants, complexity analysis, and the ability to optimize naive solutions. Interviewers often start with a simple prompt and then progressively add constraints, such as handling large inputs, many queries, or limited memory. Preparing for these questions requires not only knowing the code but also being able to explain the trade-offs and to walk through examples on a whiteboard.

Below are common interview questions that assess different facets of prime factorization algorithms. For each, we provide the core idea of the expected answer and key points to mention to demonstrate depth. Practicing these will help you articulate both the how and the why during an interview, which is often more important than writing bug-free code under time pressure.

Question 1: Write a function to return the prime factorization of n. What is its time complexity?

Expected answer: Implement optimized trial division as shown in Section 3, handling 2 separately and then testing odd divisors up to sqrt(n). Mention that the worst-case time is O(sqrt(n)) when n is prime, which is exponential in the number of bits, and space is O(log n) for the output. Discuss the 6k ± 1 optimization and why you use i * i <= n instead of computing sqrt once. Be prepared to trace the algorithm for n = 60 or n = 97.

Question 2: How would you factor 10^5 numbers up to 10^6 efficiently?

Expected answer: Do not factor each number independently with trial division, which would be O(Q * sqrt(N)). Instead, precompute smallest prime factors up to 10^6 with a sieve in O(N log log N) time and O(N) space, then factor each query in O(log n) by repeatedly dividing by spf[n]. Explain the trade-off: higher upfront memory and time for the sieve, but amortized O(1) per query after that. Mention segmented sieve if memory is constrained.

Question 3: Why does Pollard's Rho work, and when would you prefer it over trial division?

Expected answer: Explain the birthday paradox intuition: a random sequence modulo p (unknown factor) will cycle in O(sqrt(p)) steps, and gcd(|x - y|, n) reveals p when x ≡ y (mod p). Prefer Pollard's Rho when n has a large prime factor (e.g., semiprime with 10-digit primes) where trial division would need to test up to 10^10 candidates, while Rho finds the factor in about 10^5 steps. Mention that it is probabilistic, needs Miller-Rabin for primality checks, and is not deterministic.

Question 4: Given the prime factorization n = p^a × q^b, how do you compute the number of divisors and sum of divisors?

Expected answer: Number of divisors d(n) = (a+1)(b+1), sum of divisors sigma(n) = (p^(a+1)-1)/(p-1) × (q^(b+1)-1)/(q-1). Derive this from the factorization without enumerating divisors. Discuss how this is used in problems like finding highly composite numbers or perfect numbers. Emphasize that factorization is the key step that makes these computations efficient; without it, you would need to test all numbers up to n.

Question 5: How would you handle factoring a 64-bit integer that may be a product of two large primes?

Expected answer: Describe a hybrid cascade: first trial divide by small primes up to, say, 10^4 to remove small factors quickly, then use deterministic Miller-Rabin for 64-bit (with known bases) to check if the remainder is prime, and if not, apply Pollard's Rho with Brent's optimization and random restarts. Mention that pure trial division up to 2^32 is infeasible, and that Python's math.gcd and pow with modular exponentiation are implemented in C and fast enough for this. Discuss fallback to sympy or gmpy2 for even larger numbers.

Mastering these questions demonstrates not just coding ability but also system design thinking: choosing the right prime factorization algorithm for the constraints, analyzing complexity in terms of both n and bit length, and knowing when to use library support versus custom code. Interviewers value candidates who can discuss edge cases, testing strategies, and real-world applications, so always connect the algorithm back to practical use cases like cryptography, hashing, or query optimization.