Sieve and Prime Factorization

Why Primes and Factorization Show Up So Often

Prime numbers sit underneath many problems that look unrelated on the surface. Counting primes measures how many building blocks exist up to a limit. Factorization explains divisibility, greatest common divisors, least common multiples, and many graph connectivity tricks. Competitive-programming and interview questions often hide prime structure inside constraints like “many repeated divisor queries” or “numbers up to one million.” In those settings, the right preprocessing step can turn a hopeless repeated scan into a near-linear preparation followed by very cheap queries.

The two central tools are the sieve of Eratosthenes and prime factorization. The sieve answers “which numbers are prime?” for every number up to N in one preprocessing pass. Factorization answers “which primes multiply to make this number?” for one value or many values. The interesting part is that the same elimination idea supports both tasks. Once you mark composites by their smallest prime witness, you can reuse that witness later to factor numbers quickly.

The Sieve of Eratosthenes

The sieve starts with the optimistic assumption that every number from 2 to N is prime. Then it walks from left to right. When it reaches a number that is still marked prime, it knows that number really is prime, so it marks all of its multiples as composite. The elegant part is that each composite gets ruled out by its smallest prime factor. You are not testing divisibility from scratch for every number. You are letting previously discovered primes eliminate whole arithmetic progressions at once.

A common question is why the inner loop can start at p² instead of 2p. The reason is that any smaller multiple of p has the form p·k where k < p. That number was already marked when the sieve processed k or some even smaller prime factor. Starting at p² avoids duplicate work without missing any composites. This is a good example of algorithmic maturity: the main idea is elimination, and the optimization comes from understanding which eliminations have already happened.

It also helps to be clear about what the sieve is not doing. It is not “proving primality from scratch” for each value. Instead, it is maintaining a global ledger of which numbers have already been disqualified by earlier evidence. That shift from isolated tests to shared evidence is why the sieve is so efficient. A single prime discovery immediately informs the status of many future numbers.

Worked Example: Sieve and Factorization Together

Let us sieve up to 30. Start with every number from 2 to 30 marked prime. Process 2 and strike out 4, 6, 8, 10, and so on. Move to 3, which is still prime, and strike out 9, 12, 15, 18, 21, 24, 27, and 30. Skip 4 because it was already marked composite. Process 5 and strike out 25 and 30. By the time you reach numbers whose square exceeds 30, every composite has already been marked. The survivors are exactly the primes.

Now factor 756 by trial division. Divide by 2 to get 378, then by 2 again to get 189, so you already know 2² is part of the factorization. Next divide by 3 to get 63, by 3 again to get 21, and by 3 again to get 7. The remaining 7 is prime. Therefore 756 = 2² × 3³ × 7. Trial division is perfectly fine for one number when the limits are modest. The problem is repeated queries, because you do the same small divisibility work again and again.

That is where the smallest-prime-factor sieve becomes powerful. Instead of storing only a boolean “prime or not,” store spf[x], the smallest prime that divides x. During preprocessing, every composite is labeled the first time it is discovered. Then factoring a number becomes a loop: read spf[n], append it to the factor list, divide n by that prime, and repeat. You are no longer searching for divisors at query time; you are following breadcrumbs left by preprocessing.

For example, imagine spf[840] = 2. Divide to get 420, whose smallest prime factor is also 2, then 210, then 105. At 105 the smallest prime factor becomes 3, then 35 gives 5, and finally 7 ends the process. Without trial divisors, you recover 840 = 2³ × 3 × 5 × 7 just by repeatedly consulting the table. This is why SPF feels almost like a compression of many future factorizations into one preprocessing pass.

Go Implementation

The code below combines both preprocessing products: a list of primes and a smallest-prime-factor table. That makes it suitable for both counting and repeated factorization tasks.

Pattern Recognition and Caveats

Use a plain sieve when the question asks for prime counts, primality for every number in a range, or any bulk operation over all numbers up to N. Use trial division when you only need one factorization and the limits are small enough. Use an SPF sieve when many numbers need to be factored after one shared preprocessing phase. Those choices are more important than memorizing the exact inner loop bounds, because they determine whether the whole solution is shaped around one query or many.

You should also watch for derived quantities that become easy once factorization is available. GCD and LCM reasoning, divisor counts, divisor sums, radical values, and connectivity by common factors all become simpler when the prime decomposition is exposed. That is why prime preprocessing appears in such a wide variety of problems: it transforms opaque integers into structured ingredients you can manipulate deliberately.

Practice Problems

Quiz

Summary

• The sieve of Eratosthenes eliminates composites in bulk instead of testing each number independently.
• Starting from p² avoids duplicate work because smaller multiples were already handled.
• Trial division is fine for isolated factorizations at moderate limits.
• Smallest-prime-factor preprocessing turns repeated factorization into a fast lookup process.
• Prime factors are useful not only for arithmetic but also for building hidden graph connections.