Coding Grandmaster · project 8 of 46 · premium, free for now

The sieve of Eratosthenes

Write primes_below(n) using a list of True/False flags (a sieve) that returns the list of primes less than n. Print how many primes there are below 100 and the last one.

Learn

To find all primes below n, list the numbers, then cross out the multiples of 2, then of 3, then of the next number still standing, and so on. What is left are the primes. You only need to cross out multiples of numbers up to the square root of n, and you can start each time at p × p, because smaller multiples were already crossed out.

Your task

Write primes_below(n) using a list of True/False flags (a sieve) that returns the list of primes less than n. Print how many primes there are below 100 and the last one.

Stretch challenge

Count how many primes there are below 10,000 and compare with n / ln(n).

← Euclid's shortcut Digits and casting out nines →

Python

Press Run to see what your program prints.

Keep going in Coding Grandmaster

Euclid's shortcut

Write gcd_steps(a, b) returning (gcd, steps) where steps counts the remainder steps, and lcm(a, b). Print gcd_steps(48, 18) and lcm(4, 6).

Start →9

Digits and casting out nines

Write digit_sum(n) using % and //, and digital_root(n) that repeats digit_sum until one digit remains. Print both for 98765.

Start →10

Powers in a flash

Write power_steps(base, exp) that returns (result, multiplications) using repeated squaring, and pow_mod(base, exp, m) that returns base ** exp % m the same way (without ever building the full power).

Start →11

Perfect numbers

Write divisor_sum(n) (the sum of proper divisors, found by looping d up to the square root and adding both d and n // d) and print the perfect numbers below 1000.

Start →12

Counting in other bases

Write to_base(n, base) returning the digits as text, using the string "0123456789ABCDEF". Print 10 in binary and 255 in hexadecimal.

Start →

Practise the idea

🔍 Play Prime Hunter

Tap every prime, square, multiple or factor hidden in a grid of numbers.

Play now

FAQ

The sieve of Eratosthenes: common questions

I am stuck. What can I do?

Press Hint for a nudge, read the message next to each goal, and compare your code with the lesson text. If you still need it, Show answer reveals a model solution. Try to type it yourself rather than copy it.

Does my work get saved?

Your ticks and XP are saved in this browser, and in your account if you log in. The code you type is not stored on a server.

Start a conversation

Enjoying coding? Meet a teacher.

Tell us the learner's age, country and what they would like to build, and we will suggest a class. A parent or guardian can make the enquiry.

Tell us the learner’s age or grade and goals
We’ll suggest a suitable class or learning path
We’ll confirm format, timing and fees with a parent or guardian

Play it, don't just read it

Write some code right now

Free games that need no sign-up. Pick one and play for five minutes.

All free games →

Pick a game

Today's maths challengeFive questions · the same for everyone today · keep your streak goingPlay