Prime numbers are some of the simplest ideas in mathematics, yet they have fascinated mathematicians for thousands of years. They are easy to define and easy to spot when they are small, but they hide patterns and puzzles that are still studied today. They also play a quiet but important role in modern technology.
In this post we will look at what makes a number prime, how to test for primes quickly, a clever ancient method for finding them, and why they matter outside the classroom.
What is a prime number?
A prime number is a whole number greater than 1 that has exactly two factors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A whole number greater than 1 that is not prime is called a composite number, because it can be made by multiplying smaller numbers together. For example, 12 = 3 × 4.
Two details often come up in tests. First, 1 is not a prime number, because it has only one factor. Second, 2 is the only even prime. Every other even number can be divided by 2, so it has more than two factors.
Quick tests for spotting primes
To decide whether a number is prime, you check whether any smaller prime divides into it. Divisibility rules make this faster:
- A number is divisible by 2 if its last digit is even.
- A number is divisible by 3 if the sum of its digits is divisible by 3.
- A number is divisible by 5 if it ends in 0 or 5.
- A number is divisible by 11 if the alternating sum of its digits is 0 or a multiple of 11.
There is also a helpful shortcut: you only need to test primes up to the square root of the number. Take 97. Its square root is just under 10, so you only need to try 2, 3, 5 and 7. None of them divide 97 exactly, so 97 is prime. Be careful with numbers like 91, which looks prime but is actually 7 × 13.
The Sieve of Eratosthenes
One of the oldest methods for finding primes is named after Eratosthenes, a scholar of ancient Greece. Write out the numbers from 2 to 100. Circle 2, then cross out every multiple of 2. Move to the next number that is not crossed out, which is 3, circle it and cross out all its multiples. Repeat with 5 and 7. Every number left uncircled and uncrossed is prime. When you finish, you will find 25 primes below 100.
The sieve is a lovely example of an algorithm: a clear set of steps that always produces the right answer. If you enjoy that way of thinking, you might like our article on the characteristics of algorithms.
Prime factorisation
Every whole number greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. This result is known as the fundamental theorem of arithmetic. For example, 360 = 23 × 32 × 5. A factor tree is an easy way to find this: keep splitting the number into two factors until every branch ends in a prime.
Prime factorisation is more than an exercise. It is the standard method for finding the highest common factor and the lowest common multiple of two numbers, which you need when simplifying fractions or adding fractions with different denominators.
Why primes matter today
More than two thousand years ago, Euclid proved that there are infinitely many primes, and his short argument is still taught today. You can read more about thinkers like him in our post on the history of mathematics and great discoveries.
Primes also help keep information safe online. Many public-key encryption systems, such as RSA, rely on a simple imbalance: multiplying two very large primes together is quick for a computer, but working out which two primes were used, starting from their product, is extremely hard. That difference is part of what protects messages and payments on the internet.
From a times table on a classroom wall to the security of the web, prime numbers show how a simple idea can lead a very long way. Next time you see a number, try testing whether it is prime. It is a quick and satisfying bit of mental maths.
