Number Theory Basics Ladder

Who This Is For

Use this ladder when divisibility, gcd/lcm, and prime factors show up often enough that brute-force reasoning is starting to break down.

Warm-Up

• gcd and lcm
• divisors
• prime factorization of one number

Core

• SPF sieve
• many factorizations
• exponent-of-prime reasoning

Repo Anchors

• Counting Divisors

Stretch

• gcd/lcm construction problems
• CRYPTKEY
• asymptotic density with pairwise-coprime divisibility
• LAMP

Exit Criteria

You are ready to move on when you can:

• factor one number quickly and correctly
• explain gcd/lcm with prime exponents
• choose between trial division and SPF sieve
• recognize when the math part is easy and the data structure is the real challenge

External Practice

• CP-Algorithms - Linear Sieve
• CP-Algorithms - Euclidean Algorithm
• USACO Guide

Tutorial Link

• Number Theory Basics