Core Number Theory: Primes and Divisibility

Determine if a number is prime in O(sqrt(n)) time using trial division.

Implement the Sieve of Eratosthenes to find all primes up to N.

Find the prime factorization of a number in O(sqrt(n)) time.

Implement the Euclidean algorithm to compute the Greatest Common Divisor (GCD) of two integers.

Compute the Least Common Multiple (LCM) of two integers using their GCD.