Prime Numbers

4 minQuiz at the end

What is a Prime Number?

A prime number is a whole number greater than 1 that has exactly two factors: 1 and itself.

It can only be divided exactly by 1 and the number itself.

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37…

Composite Numbers

A composite number has more than two factors β€” it can be divided by numbers other than 1 and itself.

Examples: 4 (factors: 1, 2, 4), 9 (factors: 1, 3, 9), 15 (factors: 1, 3, 5, 15)

Special Cases

  • 1 is neither prime nor composite (it has only one factor: itself)
  • 2 is the only even prime number (all other even numbers are divisible by 2)

The Sieve of Eratosthenes

To find all primes up to a number:

  1. List all numbers from 2 to n
  2. Start at 2 β€” cross out all multiples of 2 (4, 6, 8…)
  3. Move to the next uncrossed number (3) β€” cross out its multiples
  4. Continue until you reach √n
  5. All uncrossed numbers are prime

Prime Factorisation

Every composite number is a unique product of prime factors:

  • 30 = 2 Γ— 3 Γ— 5
  • 48 = 2⁴ Γ— 3

This is called the Fundamental Theorem of Arithmetic.