Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 45s17 days 22 hours 18 minutes 45 seconds.

Advanced - Number Theory · 4:13

Linear Sieve & Smallest Prime Factor

The linear sieve fills lp[x], the smallest prime factor of every x up to n, writing each composite exactly once as lp[x] times a larger part whose own smallest prime is no smaller. It costs an int per number, so it is used up to about 10^7, and its real payoff is factoring any x in the table by hopping along lp[] in at most log2(x) steps.

You will learn

Implement the linear sieve that fills lp[] and the prime list in O(n), with the break at p = lp[i] and a 64-bit bound check
Explain why every composite is written exactly once, using the split x = lp[x]·y with lp[x] ≤ lp[y]
Weigh its cost honestly: 4 bytes per number versus a bitset, and no speed win over a plain Eratosthenes sieve
Factor any x ≤ n in O(number of prime factors) by following lp[], and extend the sieve to a multiplicative function such as μ

Chapters

PreviousLinear Diophantine Equations NextPrimality Tests: Trial Division, Fermat, Miller–Rabin