---
title: "Prime Numbers Explained: Sieve, Factors and Proof"
description: "Prime numbers explained: what they are, why 1 is not prime, the sieve of Eratosthenes, prime factorisation, why primes never run out, and real uses."
slug: prime-numbers-explained
canonical: https://learn.modernagecoders.com/blog/prime-numbers-explained/
date: 2026-09-28
dateModified: 2026-09-28
category: "Mathematics"
tags: ["Maths", "Prime Numbers", "Number Theory", "Python"]
keywords: ["prime numbers", "what is a prime number", "prime numbers 1 to 100", "why is 1 not a prime number", "prime factorisation", "sieve of eratosthenes", "how to check if a number is prime", "are there infinitely many primes"]
readTime: "9 min read"
author: "Modern Age Coders Team"
---
# Prime Numbers Explained

> What primes are, why 1 is not one of them, how to find them with a 2,000-year-old sieve, why they never run out, and how they protect the internet.

![Prime numbers explained: a 1 to 100 grid with the 25 primes highlighted](/images/blog/prime-numbers-explained/00-hero.png)

*By Modern Age Coders Team · 2026-09-28 · 9 min read*

**Quick answer:** A prime number is a whole number greater than 1 whose only factors are 1 and itself, such as 2, 3, 5, 7, 11 and 13. 2 is the only even prime and 1 is not prime. There are 25 primes below 100, found with the sieve of Eratosthenes by crossing out multiples. Every whole number above 1 is a product of primes in exactly one way, which is why primes are called the building blocks of arithmetic. Euclid proved there are infinitely many, and large primes secure online encryption.

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.

![The sieve of Eratosthenes applied to the numbers 1 to 100, with the 25 primes highlighted and the steps listed](/images/blog/prime-numbers-explained/01-sieve.png)

*Cross out multiples, and the primes are what survive.*

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:

**sieve.py**

```python
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,}")
```

**Output**

```text
[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,592
```

Look 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.

![Factor tree for 360 splitting into 2, 2, 2 and 45, with 360 written as 2 cubed times 3 squared times 5](/images/blog/prime-numbers-explained/02-factor-tree.png)

*Whichever way you split 360, the primes at the ends of the branches are the same.*

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:

**prime_factors.py**

```python
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 ""))
```

**Output**

```text
   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 1013
```

Prime 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](/blog/how-to-find-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.

**prime_test.py**

```python
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")
```

**Output (timings from the machine this was run on)**

```text
every divisor      prime=True   0.0684 s
up to square root  prime=True   0.0001 s
```

![Why testing divisors up to the square root is enough, with measured times for testing 999,983 both ways](/images/blog/prime-numbers-explained/04-square-root.png)

*The same answer, a small fraction of the work.*

> **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.

**euclid.py**

```python
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}")
```

**Output**

```text
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]
```

![Euclid's argument that there are infinitely many primes: products of primes plus 1 leave remainder 1 when divided by each prime](/images/blog/prime-numbers-explained/03-infinite.png)

*Remainder 1 every time, so a new prime factor must exist.*

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](/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](/online-maths-tuition) 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.

[Book a free class](/book-demo) [Book a priority demo](/book-demo)

## Frequently asked questions

**What is a prime number?**

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.

**Why is 1 not a prime number?**

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.

**Is 2 a prime number?**

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.

**How many prime numbers are there between 1 and 100?**

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.

**How do you check if a large number is prime?**

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.

**What is prime factorisation?**

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.

**Are there infinitely many prime numbers?**

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.

---

*Source: https://learn.modernagecoders.com/blog/prime-numbers-explained/*