Prime Number Sieve

Watch the Sieve of Eratosthenes cross out multiples live — each prime in its own colour — then check whether any number up to 1012 is prime and see all its factors.

Class 4–8 Animated, step by step Up to 1000 Prime checker

The Sieve of Eratosthenes finds prime numbers by crossing out multiples. Circle 2 and cross out every multiple of 2; the next number left (3) is prime, so cross out its multiples, then repeat with 5, 7 … until p × p is bigger than your limit. Everything still uncrossed is prime. There are 25 primes below 100 and 168 below 1000.

Sieve controls

Choose how far to search, then press play.

Press Play to start.
Tap any number to see why it is prime or composite.

Primes found

They appear here as the sieve finds them.

Is it prime? Checker

Any whole number up to 1012 (1,000,000,000,000). Uses trial division up to √n.

Why stop at √n?

The idea that makes both the sieve and the checker fast.

Factors come in pairs that multiply to the number. In every pair, one factor is at most √n and the other is at least √n — they meet exactly at √n.

    How it works

    Find primes the way Eratosthenes did

    Over 2,200 years ago a Greek mathematician found a clever way to list primes without dividing a single number.

    Pick a limit

    Choose how far to search — 100 is perfect for class, 1000 shows the bigger pattern.

    Press play

    Watch each new prime get circled and its multiples crossed out in that prime’s colour.

    Step through

    Use “Next prime” to pause after each prime, and tap any number to see its factors.

    Check big numbers

    Use the checker for any number up to one lakh crore (1012).

    The sieve, step by step

    1. Write the numbers 2 to N. (1 is neither prime nor composite.)
    2. Circle 2 — it is prime. Cross out every multiple of 2.
    3. The next number not crossed out (3) is prime. Cross out its multiples.
    4. Repeat with 5, 7, … until p × p is bigger than N. Everything left is prime.

    Why start crossing at p × p?

    Take 7. Its smaller multiples 14, 21, 28, 35 and 42 are 2 × 7, 3 × 7, 4 × 7, 5 × 7 and 6 × 7 — each has a smaller factor, so it was already crossed out. The first new one is 7 × 7 = 49.

    Twin primes and other patterns

    Twin primes differ by 2: (3, 5), (11, 13), (17, 19), (41, 43). Every prime bigger than 3 is one more or one less than a multiple of 6 — set the grid to 6 per row and they line up in two columns.

    Key facts to remember

    • 2 is the only even prime.
    • There are 25 primes below 100 and 168 below 1000.
    • Every whole number above 1 is a product of primes in exactly one way (Fundamental Theorem of Arithmetic).
    Classroom idea: give each group a printed 1–100 grid and a colour per prime, run the sieve on the smartboard at slow speed, and let students cross out along with it. Then ask: why did we never need the colour for 11?
    Questions & answers

    Prime Number Sieve — your questions

    What is the Sieve of Eratosthenes?

    It is a method for listing prime numbers without dividing anything. Write out 2 to N, circle 2 as prime and cross out all its multiples, then circle the next uncrossed number and cross out its multiples. Keep going until the circled prime squared passes N; every number left uncrossed is prime.

    How many prime numbers are there between 1 and 100?

    There are 25: 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. Below 1000 there are 168 primes. The number 1 is neither prime nor composite, and 2 is the only even prime number.

    How do I check whether a number is prime by hand?

    Divide it only by the primes up to its square root. For 91, test 2, 3, 5 and 7 — since 7 × 13 = 91, it is composite, not prime. Factors always come in pairs that multiply to the number, and in every pair one factor is at most √n, so there is no need to test any further.

    Why does the sieve start crossing out at p × p?

    Because the smaller multiples have already gone. Take 7: its multiples 14, 21, 28, 35 and 42 are 2 × 7, 3 × 7, 4 × 7, 5 × 7 and 6 × 7, and each was crossed out when 2, 3 and 5 were processed. The first new multiple of 7 is 7 × 7 = 49, so that is where crossing out begins.

    What are twin primes?

    Twin primes are two primes that differ by 2, such as (3, 5), (11, 13), (17, 19) and (41, 43). Tick Highlight twin primes to mark them on the grid. Every prime bigger than 3 is one more or one less than a multiple of 6, so setting the grid to 6 numbers per row lines them up in two neat columns.

    What is the Fundamental Theorem of Arithmetic?

    It says every whole number above 1 can be written as a product of prime numbers in exactly one way, apart from the order. For example 84 = 2 × 2 × 3 × 7 and there is no other set of primes that multiplies to 84. This is why primes are called the building blocks of all numbers.