Prime numbers and a removal game
Lesson 11 of 11
11Prime numbers and a removal game
The big pictureThe removal game looks complex, but each turn removes one prime with its multiples, so the number of turns equals the number of primes. The whole game turns into one question: is that count odd or even?
What the picture shows: The sieve: for each prime you find, cross out its multiples. What stays uncrossed is prime. Numbers up to the square root of n are enough.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
A prime is divisible only by 1 and itself, like 2, 3, 5 and 7. To find every prime up to 30, write the numbers, cross out all multiples of 2 (4, 6, 8...), then of 3, then of 5. What remains are the primes, without dividing a single number yourself.
The sieve is O(n log log n) time and O(n) memory, and crossing out starts at p*p because smaller multiples were already crossed by smaller factors. prefix[i] = the count of primes ≤ i, so counting primes in [1, n] is prefix[n]. For many questions: sieve once up to max(n). In turn-based games with optimal play, if the number of moves is fixed whatever the players do, parity decides the winner: odd means the first player wins, even means the second.
Before You Start
🔁Loops and lists
You write stepped loops: range(a, b, step).
➗Remainder
You know %, even and odd.
The Core Idea
1The Sieve of Eratosthenes
A true/false list for every number, crossing out multiples in steps of p:
def sieve(n):
is_prime = [False, False] + [True] * (n - 1)
p = 2
while p * p <= n:
if is_prime[p]:
for m in range(p * p, n + 1, p):
is_prime[m] = False
p += 1
return is_prime
flags = sieve(30)
print([i for i, ok in enumerate(flags) if ok])2The prefix sum
After the sieve, prefix[i] holds the count of primes up to i. Any "how many primes up to n?" question becomes reading one cell:
def sieve(n):
is_prime = [False, False] + [True] * (n - 1)
for p in range(2, int(n ** 0.5) + 1):
if is_prime[p]:
for m in range(p * p, n + 1, p):
is_prime[m] = False
return is_prime
questions = [5, 10, 1, 30]
flags = sieve(max(questions))
prefix, running = [], 0
for ok in flags:
running += ok
prefix.append(running)
for n in questions:
print(n, "->", prefix[n], "primes")3Exercise: who wins?
A game: the numbers 1 to n are on the table. Two players take turns, and each turn the player picks a remaining prime and removes it with all its multiples. Whoever cannot find a prime loses. Notice each turn removes exactly one prime (its multiples are not prime), so the number of turns = the number of primes up to n. Write a function that takes a list of questions (values of n) and returns who won more rounds, using the sieve and the prefix sum. Test: n = 1 has no primes, so the first player loses.
Worked example
Problem: n = 6. Analysis: primes 2, 3 and 5. Turn 1: the first player removes 2 (with 4 and 6). Turn 2: the second removes 3. Turn 3: the first removes 5. Turn 4: the second finds no prime. Result: 3 turns, odd, the first player wins, and no simulation was needed: prefix[6] = 3 is enough.
Myth vs Reality
| Myth | Reality |
|---|---|
| 1 is a prime. | No. A prime has exactly two different divisors, and 1 has only one. |
| You must simulate the game move by move. | The number of moves is fixed, so parity is enough. |
Where you meet it at work
🔐Cryptography
RSA rests on large primes.
#️⃣Hash tables
Prime sizes reduce collisions in some designs.
Test your understanding
Why does crossing out start at p*p?
For example 2×5 was crossed at 2, so with 5 we start at 25.
How many primes are there up to 10?
2, 3, 5 and 7.
In the game, n = 10. Who wins?
4 primes, an even count, so the second player takes the last turn.
Quick review cards
Check Your Understanding
Why stop at √n?
Because any composite ≤ n has a factor ≤ √n, so it was already crossed out.
A hundred questions with different n, how many sieves?
Just one, up to the largest n.
What if n = 1?
No primes, so the first player has no move and loses.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Done with this lesson?
Sign in to save your progress.