Table of Contents
Prime numbers are the building blocks of arithmetic. Every whole number bigger than 1 is either a prime or can be made by multiplying primes together, in exactly one way. That simple fact sits underneath fractions, HCF and LCM, and the encryption that protects every online payment you have ever made. Primes are also one of the few topics where a 10-year-old and a professional mathematician can be interested in the same question.
This guide explains what prime numbers are, why 1 is not one of them, how to find primes with a 2,000-year-old method, how to break any number into its prime factors, why there are infinitely many primes, and where they are used in real life. Every list, count and factorisation here was produced by running the Python code shown alongside it.
What a prime number is
A prime number is a whole number greater than 1 that can only be divided exactly by 1 and by itself. 7 is prime: the only whole numbers that divide it are 1 and 7. 8 is not: it can also be divided by 2 and 4. Numbers greater than 1 that are not prime are called composite.
A helpful way to picture it: try to arrange a number of counters into a rectangle with more than one row. 12 counters make a 3 by 4 rectangle, so 12 is composite. 7 counters can only make a single line, 1 by 7, so 7 is prime.
- 2 is the only even prime. Every other even number can be divided by 2, so it has at least three factors.
- 1 is not prime. It has only one factor, itself. Mathematicians exclude it on purpose, because including it would break the rule that every number has only one prime factorisation (you could add as many 1s as you liked).
- 0 is not prime, and negative numbers are not counted as prime either.
Finding primes: the sieve of Eratosthenes
Over two thousand years ago, the Greek scholar Eratosthenes described a method for finding every prime up to a limit, and it is still one of the best. Write out the numbers, then cross out every multiple of 2 except 2, every multiple of 3 except 3, and so on. Whatever survives is prime.
You only need to sieve with primes up to the square root of your limit. For 100 that means 2, 3, 5 and 7, because any composite number below 100 must have a factor of 7 or less. Here is the sieve in Python, used to list the primes below 100 and to count them further out:
def primes_up_to(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
for p in range(2, int(n ** 0.5) + 1):
if is_prime[p]:
for multiple in range(p * p, n + 1, p):
is_prime[multiple] = False # cross out every multiple of p
return [x for x in range(n + 1) if is_prime[x]]
print(primes_up_to(100))
for limit in (100, 1_000, 10_000, 100_000):
print(f"primes below {limit:>7,}: {len(primes_up_to(limit)):>5,}")[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
primes below 100: 25
primes below 1,000: 168
primes below 10,000: 1,229
primes below 100,000: 9,592Look at how the counts thin out. A quarter of the numbers below 100 are prime, but only about one in ten below 100,000. Primes get rarer as numbers get bigger, but, as we will see, they never stop.
| Below | Number of primes | Share of numbers |
|---|---|---|
| 100 | 25 | 25.0% |
| 1,000 | 168 | 16.8% |
| 10,000 | 1,229 | 12.3% |
| 100,000 | 9,592 | 9.6% |
Prime factorisation and factor trees
Every whole number greater than 1 can be written as a product of primes, and there is only one way to do it, apart from the order. This is called the fundamental theorem of arithmetic, and it is why primes are described as the atoms of arithmetic.
To find the prime factors by hand, draw a factor tree: split the number into any two factors, then keep splitting each branch until every branch ends in a prime. The program below does the same thing by dividing by 2 as many times as it can, then 3, then 5, and so on:
def prime_factors(n):
factors, p = [], 2
while n > 1:
while n % p == 0: # divide by p as many times as it goes
factors.append(p)
n //= p
p += 1
return factors
for n in (60, 84, 97, 360, 1001, 2026):
f = prime_factors(n)
print(f"{n:>5} = {' x '.join(map(str, f))}" + (" (prime)" if len(f) == 1 else "")) 60 = 2 x 2 x 3 x 5
84 = 2 x 2 x 3 x 7
97 = 97 (prime)
360 = 2 x 2 x 2 x 3 x 3 x 5
1001 = 7 x 11 x 13
2026 = 2 x 1013Prime factorisation is how HCF and LCM are found in school maths: the HCF uses the primes two numbers share, and the LCM uses every prime either needs. Our guide to finding HCF and LCM in Python shows five methods, including this one.
A faster way to test whether a number is prime
To check whether a number is prime, you might try dividing by every number below it. That works but is wasteful. Factors come in pairs, and in every pair one factor is at most the square root of the number. So if nothing up to the square root divides it, nothing will. For a number around a million, that means trying about a thousand divisors instead of a million.
from time import perf_counter
def is_prime_slow(n): # try every number below n
return n > 1 and all(n % d for d in range(2, n))
def is_prime_fast(n): # only try up to the square root
return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))
n = 999_983 # the largest prime below one million
for name, test in (("every divisor", is_prime_slow), ("up to square root", is_prime_fast)):
start = perf_counter()
result = test(n)
print(f"{name:<18} prime={result} {perf_counter() - start:.4f} s")every divisor prime=True 0.0684 s
up to square root prime=True 0.0001 s
Quick divisibility checks
Before dividing, rule out the easy ones. Even numbers (except 2) are not prime. If the digits add up to a multiple of 3, the number is divisible by 3. If it ends in 0 or 5, it is divisible by 5. These three checks catch most composite numbers instantly.
Why there are infinitely many primes
Around 300 BCE, Euclid proved that the primes never run out, and his argument is short enough for a curious 12-year-old to follow. Suppose you had a complete list of all the primes. Multiply them all together and add 1. The new number leaves a remainder of 1 when divided by every prime on your list, so none of them divides it. But every number above 1 has at least one prime factor, so there must be a prime that is not on your list. The list was not complete after all, and that is true of every list.
from math import prod
# Euclid's idea: multiply some primes together and add 1.
# The result is not divisible by any of them, so a new prime must exist.
for primes in ([2, 3], [2, 3, 5], [2, 3, 5, 7], [2, 3, 5, 7, 11, 13]):
n = prod(primes) + 1
leftovers = [n % p for p in primes]
print(f"{' x '.join(map(str, primes))} + 1 = {n:>5} remainders: {leftovers}")2 x 3 + 1 = 7 remainders: [1, 1]
2 x 3 x 5 + 1 = 31 remainders: [1, 1, 1]
2 x 3 x 5 x 7 + 1 = 211 remainders: [1, 1, 1, 1]
2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031 remainders: [1, 1, 1, 1, 1, 1]
One subtlety worth noticing: the new number is not always prime itself. 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031, which equals 59 x 509. But 59 and 509 are both primes that were not on the list, which is exactly what the proof needs.
Where prime numbers are used
- Online security. The RSA encryption system, used for decades to protect websites and payments, relies on the fact that multiplying two very large primes is easy, but splitting the result back into those primes is extremely hard. Your browser relies on problems like this every time you see a padlock.
- Hashing and computing. Programmers often use prime sizes for hash tables and in random number generators, because primes help spread values evenly.
- Nature. Some species of periodical cicadas in North America emerge every 13 or 17 years, both primes. One explanation biologists have proposed is that prime cycles make it harder for predators with shorter cycles to sync up with them.
- Puzzles and competitions. Primes appear constantly in maths olympiad problems, from the simplest divisibility question to deep number theory.
Primes are the one topic where a ten-year-old can ask a question that nobody on Earth knows the answer to.
That quote is literally true. Nobody knows whether there are infinitely many twin primes, pairs like 11 and 13 that differ by 2, even though mathematicians have been trying to prove it for centuries.
How we teach it
Primes fit the first principle on our how we teach page especially well: start with a spark, a question worth wondering about, before any theory arrives. They appear in our live maths classes and in our coding courses, where they make excellent first algorithm problems. Classes are one to one or in small groups of 5 to 10.
Frequently asked questions
A prime number is a whole number greater than 1 that has exactly two factors: 1 and itself. Examples are 2, 3, 5, 7, 11 and 13. A number with more than two factors, such as 12, is called composite.
Because it has only one factor, itself, and a prime needs exactly two. Excluding 1 also keeps the rule that every whole number has only one prime factorisation. If 1 were prime, you could add any number of 1s to a factorisation.
Yes. 2 is the smallest prime and the only even prime. Its only factors are 1 and 2. Every other even number is divisible by 2, so it cannot be prime.
There are 25 prime numbers below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
Divide it by each prime up to its square root. If none of them divides it exactly, the number is prime. For example, to test 97 you only need to try 2, 3, 5 and 7, because the square root of 97 is just under 10.
Writing a number as a product of prime numbers, for example 360 = 2 x 2 x 2 x 3 x 3 x 5. Every whole number greater than 1 has exactly one prime factorisation, which is called the fundamental theorem of arithmetic.
Yes. Euclid proved it around 300 BCE: multiply any list of primes together and add 1, and the result must have a prime factor that is not on the list. So no list of primes can ever be complete.
