- Mathematics
- Class 11
- Project 15
15The Prime Sieve: Building an Algorithm by Hand and in Code
Students build a large 1–100 board and run the Sieve of Eratosthenes by hand, crossing out multiples of 2, 3, 5 and 7 with different colours. They discover why they can stop at 7, write the steps as a precise algorithm (flowchart and pseudocode), and then turn it into a short program that finds all primes up to 10,000. They compare the sieve with testing each number one by one.
- Class and age
- Class 11 · 16–17
- Activity type
- Individual or group
- Time needed
- 60–90 minutes
- Difficulty
- Medium
- Estimated budget
- ৳0–৳50
Mathematical concepts
- Prime and composite numbers
- Why checking up to √n is enough
- Algorithms: flowcharts, pseudocode and loops
- Counting primes and their thinning out
- Comparing algorithm efficiency
Learning objectives
- Carry out the sieve accurately by hand.
- Explain the √n stopping rule.
- Write and run an algorithm as code.
- Explore how primes become rarer.
Real-life connection
Large prime numbers protect online banking and messaging. Computers generate and test primes with algorithms that grew from simple ideas like the sieve.
Materials required
- Chart paper with a 10 × 10 grid of numbers 1–100
- Four coloured markers
- A computer or phone with a free Python environment (or paper pseudocode if no device is available)
Step-by-step instructions
- Make the 1–100 board. Cross out 1 (it is not prime).
- Circle 2, then cross out every multiple of 2 in one colour.
- Circle the next number not crossed out (3) and cross out its multiples in a new colour. Repeat for 5 and 7.
- Notice that after 7, no new numbers are crossed out. Explain why using 11 × 11 = 121 > 100.
- Count the primes up to 100 (there are 25). Count how many are in each row of ten.
- Write the sieve as a flowchart, then as pseudocode with loops.
- Write the program and run it for 1,000 and 10,000. Count the primes found.
- Compare the time with a program that tests each number by dividing. Which is faster, and why?
Mathematical explanation
Every composite number up to 100 has a factor no bigger than its square root, which is at most 10, so its smallest prime factor is 2, 3, 5 or 7. Crossing out multiples of these four primes therefore removes every composite number, and what is left are the 25 primes below 100. The sieve is efficient because it never divides: it simply steps through multiples. Running it further shows primes thinning out: 25 below 100, 168 below 1,000 and 1,229 below 10,000, yet they never run out, as Euclid proved more than two thousand years ago.
Expected project output
A coloured sieve board, a flowchart and pseudocode, a working program with prime counts, and a speed comparison.
Skills developed
- Number theory
- Algorithm design and coding
- Pattern finding
- Efficiency thinking
Assessment criteria
- The sieve board is accurate.
- The √n stopping rule is explained.
- The algorithm is written clearly and the program works.
- The efficiency comparison is reasoned.
Extension challenge
Use your program to find twin primes (pairs like 11 and 13) below 10,000. Do they also thin out?
Safety and inclusion
Use school or family devices with permission and install software only with an adult's approval.