Engineering Fluency OS

Why This Matters

Every integer greater than 1 is either prime or can be broken down into primes. A prime number has exactly two factors: 1 and itself. The number 7 is prime because nothing divides it evenly except 1 and 7. The number 12 is not prime because it can be factored as 2 x 2 x 3. This decomposition into prime building blocks is called prime factorization, and it is unique for every number.

Understanding factors is essential for simplifying fractions, finding common denominators, and solving equations. The greatest common divisor (GCD) of two numbers is the largest factor they share. For 12 and 18, the GCD is 6. This concept powers fraction simplification: to reduce 12/18, divide both by their GCD (6) to get 2/3.

In computer science, prime numbers are the backbone of cryptography. RSA encryption relies on the fact that multiplying two large primes is easy, but factoring the result back into those primes is extraordinarily hard. The Euclidean algorithm for computing GCD is one of the oldest algorithms still in daily use, dating back over 2,300 years. It is elegant, efficient, and a beautiful example of how simple mathematical ideas power modern technology.

Define Terms

Visual Model

60composite number

2prime factor

30composite

2prime factor

15composite

3prime factor

5prime factor

60 = 2 x 2 x 3 x 5prime factorization

GCD(60, 48) = 12largest shared factor

The full process at a glance. Click Start tour to walk through each step.

A factor tree breaks 60 into its prime factors: 2 x 2 x 3 x 5. The GCD uses shared prime factors to find the largest common divisor.

Code Example

Code

// Check if a number is prime
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}
console.log(isPrime(7));   // true
console.log(isPrime(12));  // false
console.log(isPrime(2));   // true
console.log(isPrime(1));   // false

// Find all factors of a number
function factors(n) {
  const result = [];
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) result.push(i);
  }
  return result;
}
console.log(factors(12));  // [1, 2, 3, 4, 6, 12]
console.log(factors(7));   // [1, 7] (prime!)

// Prime factorization
function primeFactors(n) {
  const result = [];
  let d = 2;
  while (n > 1) {
    while (n % d === 0) {
      result.push(d);
      n = n / d;
    }
    d++;
  }
  return result;
}
console.log(primeFactors(60));   // [2, 2, 3, 5]
console.log(primeFactors(100));  // [2, 2, 5, 5]

// GCD using the Euclidean algorithm
function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}
console.log(gcd(60, 48));   // 12
console.log(gcd(100, 75));  // 25
console.log(gcd(17, 13));   // 1 (coprime)

Interactive Experiment

Try these exercises:

List all primes less than 30. How many are there? Do you notice any patterns in their spacing?
Find the prime factorization of 84 and 90. What primes do they share? Use those to compute the GCD.
Trace the Euclidean algorithm by hand for GCD(252, 105). Write each step: 252 = 2 x 105 + 42, then 105 = 2 x 42 + 21, then 42 = 2 x 21 + 0. So GCD = 21.
Is 1 a prime number? Research why mathematicians exclude it from the primes.
Find two numbers whose GCD is 1 (coprime numbers). What does it mean for fraction simplification when the GCD is 1?

Quick Quiz

Coding Challenge

Euclidean GCD

Write a function called `euclideanGCD` that takes two positive integers and returns their greatest common divisor using the Euclidean algorithm. The algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero value is the GCD. For example: GCD(48, 18) -> GCD(18, 12) -> GCD(12, 6) -> GCD(6, 0) = 6.

Loading editor...

Real-World Usage

Factors and primes have profound applications:

RSA cryptography: The security of HTTPS, SSH, and digital signatures relies on the difficulty of factoring large numbers (hundreds of digits) into their prime components.
Hash tables: Hash functions often use prime-sized tables because primes distribute keys more evenly, reducing collisions.
Fraction simplification: Every time a calculator or program simplifies a fraction, it computes the GCD of the numerator and denominator.
Least common multiple: Scheduling systems compute LCM to find when periodic events coincide. LCM(a,b) = a * b / GCD(a,b).
Error-correcting codes: Reed-Solomon codes (used in QR codes and CDs) rely on arithmetic in prime fields. Primes ensure the math works correctly.

Factors and Primes