Primes

2 articles

dsa6 min read

Sieve of Eratosthenes — Generate All Primes Up to N in O(n log log n)

LC 204 Count Primes is the gateway sieve problem at Google and Amazon. Master the Sieve of Eratosthenes, understand why you start marking at p*p, and apply the technique to interval queries, prime factorization, and every sieve variant an interviewer can ask.

March 19, 2026Read →

dsa8 min read

Prime Factorization Explained — Trial Division, Smallest Prime Factor Sieve in O(log n) [LC 952, Amazon, Microsoft]

Prime factorization is the workhorse of number-theoretic interview problems at Amazon and Microsoft. Master trial division in O(sqrt n), the smallest-prime-factor sieve for batched factorization in O(log n) per query, and the divisor-counting tricks they unlock.

March 19, 2026Read →