Number Theory Checkpoint

1. Euclid's algorithm repeatedly uses:

Remainders (a % b) Sorting Exponentiation Prime factorization

2. LCM formula is lcm(a,b) = a / gcd(a,b) * b.

3. Binary exponentiation runs in:

O(log exp) O(exp) O(n log n) O(1)

4. In the sieve, for prime p you start marking at:

p*p 2*p p+1 p-1