Basic Math: Divisibility, GCD, Primes
Divisibility, GCD and LCM, primes, the sieve of Eratosthenes and prime factorization.
The competitive programmer's number-theory base consists of four topics.
1. Divisibility and remainders. a is divisible by b when a % b == 0. Remainders cycle: the last digit of a number is n % 10, its parity is n % 2.
2. GCD and LCM. The greatest common divisor is computed with Euclid's algorithm in O(log n) (you wrote it in the language course). The least common multiple: LCM(a,b) = a / GCD(a,b) * b — in exactly that order, to avoid overflow.
3. Primes. Testing a single number — trying divisors up to the square root. And when you need ALL primes up to n — the sieve of Eratosthenes: write out the numbers and cross out the multiples of each prime.
The sieve of Eratosthenes: all primes up to n. Enter: 50
Why the sieve is fast: every composite number is crossed out by its prime divisors, giving O(n log log n) in total — almost linear. For n = 10⁷ it runs in under a second.
A subtlety: crossing out starts from i * i, not from 2 * i — all smaller multiples have already been crossed out by smaller primes.
4. Prime factorization: divide the number by every divisor up to the square root; if something greater than one remains — it is the last prime factor.
Prime factorization. Enter: 360
Task: use the sieve to count how many primes are below one million (answer: 78498 — check yourself).
Then solve the attached problems "GCD of Two Numbers", "Prime Check" and "Factorial" — and mark the lesson as completed.