Prime and composite numbers

Once you know how to count factors, every whole number from 2 onwards falls into one of two camps: prime or composite.

The definitions

The number 1 has only one factor (itself), so it doesn't fit either definition. By convention, it is neither prime nor composite.

The first few primes

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Some things to notice:

• 2 is the only even prime. Every other even number is divisible by 2 (so it has 1, 2, and itself as factors — at least three).
• The primes get rarer as you go higher.
• The primes never end — there's no biggest prime number. People have proved this mathematically over two thousand years ago.

How to test whether a number is prime

To check whether a number n is prime, try dividing it by the small primes one at a time:

1. Is it divisible by 2? If yes and n ≠ 2, it's composite.
2. Is it divisible by 3? If yes and n ≠ 3, it's composite.
3. By 5? By 7? Continue with the next prime…

Stop once the prime you are testing is larger than $\sqrt{n}$. If no prime ≤ $\sqrt{n}$ divides n, then n is prime.

Is 37 prime?

$\sqrt{37}$ ≈ 6.1, so test primes 2, 3, 5.

• 37 ÷ 2 = 18 r 1 ✗
• 37 ÷ 3 = 12 r 1 ✗
• 37 ÷ 5 = 7 r 2 ✗

No prime up to 6 divides 37, so 37 is prime.

The sieve of Eratosthenes

To find all primes up to a limit (say, 50):

1. Write the numbers 2 to 50 in a grid.
2. Circle 2 (it's prime), then cross out every other multiple of 2: 4, 6, 8, …
3. Find the next number still standing (3). Circle it, then cross out every other multiple: 6, 9, 12, … (some are already crossed)
4. The next standing number is 5. Circle it, cross out 10, 15, 20, …
5. Repeat with 7. Once you reach √50 ≈ 7, you're done — every number left standing is prime.

This trick is over 2 000 years old. It's named after Eratosthenes, a Greek mathematician.

What's next

• For parents
• Back to the introduction
• Finding factors

Try it out

• 🧐 Prime or composite? — decide for numbers up to 50
• 🔢 List all factors of a number