Prime Factor Extraction

Primes and factorization underpin GCD structure, sieve precomputation, and counting problems with unique prime exponents.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Sieve marks composites up to n in O(n log log n). Trial division checks factors up to √n. SPF table answers smallest prime factor queries fast.

Try this in Python

def sieve(n: int) -> list[bool]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return is_prime


print(sum(sieve(30)))

Common mistakes

• Sieve array size off-by-one.
• Treating 1 as prime.
• Trial division without skipping even numbers after 2.

Key takeaways

• Precompute SPF up to max coordinate in problem.
• Factor n by dividing by SPF[n] repeatedly.