Prime Factorization & Sieve Visualizer

A prime number is a whole number greater than 1 that has exactly two divisors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23...

2 is the only even prime. All other even numbers are divisible by 2, so they are composite. There are infinitely many primes, as Euclid proved around 300 BCE.

The prime-counting function $\pi(n)$ counts primes up to $n$. It grows roughly as $n / \ln n$ by the Prime Number Theorem.

Every integer greater than 1 is either prime or can be written as a unique product of prime numbers (up to the order of the factors). This is the Fundamental Theorem of Arithmetic.

A factor tree finds prime factors by repeatedly splitting a composite number. Every path from root to leaf ends at a prime. No matter how you split, you always get the same set of primes.

The Sieve of Eratosthenes is an ancient algorithm for finding all primes up to a limit $n$. The steps:

1. Write out numbers 2 through $n$.
2. Find the first unmarked number (a prime). Cross out all its multiples starting from its square.
3. Repeat until you reach $\sqrt{n}$. All remaining unmarked numbers are prime.

The Greatest Common Divisor (GCD) is the largest number that divides both $a$ and $b$. The Least Common Multiple (LCM) is the smallest number divisible by both.

Using prime factorizations, take the product of shared primes (minimum exponents) for the GCD, and the product of all primes (maximum exponents) for the LCM. The identity $\gcd(a,b) \times \text{lcm}(a,b) = a \times b$ always holds.