Python Module 3 – Control flow: decisions, loops and pattern matching
Solving problems with loops step by step
Plan a loop by its inputs, invariant and exit condition, then solve primes, Euclid's GCD, digit sums and Armstrong numbers, and measure how the work grows.
What you will learn
- Plan a loop with its inputs, invariant and exit condition
- Implement classic number problems such as primes, GCD and digit sums
- Test a loop on its edge cases, such as 0, negative numbers and the squares of primes
- Estimate how running time grows with input size
Before you start
What you’ll learn · Before you start
What you will learn
- Plan a loop with its inputs, invariant and exit condition
- Implement classic number problems such as primes, GCD and digit sums
- Test a loop on its edge cases, such as 0, negative numbers and the squares of primes
- Estimate how running time grows with input size
Before you start
On this page
Many small programming problems are loops in disguise: is 97 a prime, what is the greatest common divisor (gcd): The largest whole number that divides two numbers exactly: gcd(1071, 462) is 21. Euclid's algorithm finds it, and math.gcd() computes it. of 1071 and 462, what do the digits of 9475 add up to. Each needs only a few lines of Python, and the hard part is rarely the syntax. It is deciding what the loop should do on each pass and when it should stop. So each problem below is planned first, in plain words, then written as code, then measured as the numbers get bigger.
You can step through the loops on the very numbers the text works with, watch what stays true on every pass, and see
how a missing + 1 makes a prime test call 25 a prime without any error.
Plan the loop first: what changes, what stays true, when it stops
Take a small problem: add up the decimal digits of a whole number, so 9475 gives 9 + 4 + 7 + 5 = 25. Before writing any code, answer four questions:
- What goes in and what comes out? A whole number
nthat is 0 or more; the sum of its digits. - What changes on each pass? One digit moves out of
nand into a runningtotal:n % 10is the last digit andn //= 10drops it. - What stays true at the start of every pass?
totalplus the digit sum of what is left innalways equals the answer. A statement like this, true before and after every pass, is called the loop’s invariant: A statement about a loop's variables that is true at the start of every pass, such as total plus the digit sum of what is left in n equals the answer. When the loop stops, it says why the result is right.. - When does it stop? When
nis 0, no digits are left, so by the invarianttotalis the answer.
Step through the loop for 9475 with those four answers in mind. At each loop test, add total to the digits still
in n:
Program · digit_sum_trace.py
n = 9475
total = 0
while n > 0:
total += n % 10
n //= 10
print(total) Variables
- changed in this step
Printed so far
Nothing printed yet25
Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.
The drawing shows the variables when the program ends, and the program's 17 steps are listed below.
Change the program and run it here. Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Every step as text
- Start. No line has run yet, so there are no variables. Python starts with line 1.
- Line 1.
n = 9475setsnto9475. - Line 2.
total = 0setstotalto0. - Line 3.
while n > 0:tests its condition: it is true (nis9475), so the body runs. Key point Before the first pass total is 0 and the digits of n, 9475, add up to 25: 0 + 25 = 25, the answer. That sum is the invariant. - Line 4.
total += n % 10changestotalfrom0to5. - Line 5.
n //= 10changesnfrom9475to947. - Line 3.
while n > 0:tests its condition: it is true (nis947), so the body runs again (pass 2). One digit, 5, has moved from n to total: 5 + (9 + 4 + 7) = 25 again. - Line 4.
total += n % 10changestotalfrom5to12. - Line 5.
n //= 10changesnfrom947to94. - Line 3.
while n > 0:tests its condition: it is true (nis94), so the body runs again (pass 3). 12 + (9 + 4) = 25. n loses a digit on every pass, and total gains it, so the sum stays the same. - Line 4.
total += n % 10changestotalfrom12to16. - Line 5.
n //= 10changesnfrom94to9. - Line 3.
while n > 0:tests its condition: it is true (nis9), so the body runs again (pass 4). 16 + 9 = 25, with one digit left in n. - Line 4.
total += n % 10changestotalfrom16to25. - Line 5.
n //= 10changesnfrom9to0. - Line 3.
while n > 0:tests its condition: it is false (nis0), so the loop ends. n is 0, so n > 0 is False and the loop stops. No digits are left, so by the invariant total, 25, is the answer. - Line 6.
print(total)prints25. That was the last line, so the program ends.
The sum was 25 at every test, and when n reached 0 nothing was left to add: the plan’s argument, carried out by the
loop itself.
The code follows from the plan line by line. The program also traces the loop for 9475 and checks the invariant at the top of each pass:
def digit_sum(n):
"""Add up the decimal digits of a whole number n that is 0 or more."""
total = 0
while n > 0:
total += n % 10 # add the last digit
n //= 10 # then drop it
return total
# Trace the loop for 9475, and check the invariant at the top of every pass.
n, total = 9475, 0
while n > 0:
print(f"n = {n:<5} total = {total:<3} total + digit_sum(n) = {total + digit_sum(n)}")
total += n % 10
n //= 10
print(f"n = {n:<5} total = {total:<3} n is 0, so the loop stops")
print(digit_sum(9475), digit_sum(7), digit_sum(0), digit_sum(-25)) Output
n = 9475 total = 0 total + digit_sum(n) = 25 n = 947 total = 5 total + digit_sum(n) = 25 n = 94 total = 12 total + digit_sum(n) = 25 n = 9 total = 16 total + digit_sum(n) = 25 n = 0 total = 25 n is 0, so the loop stops 25 7 0 0
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 digit_sum.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The last column stays 25 on every line: that is the invariant at work, and seeing it hold is a quick way to trust a
loop. Two edge cases are worth checking for every loop: the smallest inputs and the ones the plan did not expect. For
0 the loop never runs and the answer, 0, is right. For -25 it also never runs, and 0 is wrong. The plan said
“0 or more”, so either refuse negative numbers with an error or work with abs(n).
Key idea
Plan a loop by four answers before you write it: what goes in and comes out, what changes on each pass, what stays true, and when it stops.
Checkpoint
Check: Planning a loop with an invariant
Trial division can stop at the square root
A prime is a whole number above 1 whose only divisors are 1 and itself. The direct test,
trial division: Testing whether n is prime by trying the possible divisors one by one, from 2 up to the integer square root of n, and stopping at the first one that divides n exactly., tries the possible divisors one by one and stops at the first one
that divides exactly, because one divisor is enough to prove the number is not prime. The lesson on while loops wrote
this search as while divisor * divisor <= n; here it is with for and range(), together with the reason why it
never needs to try anything above the square root of n:
Why trial division can stop at the square root of n
Text description of the diagram
The diagram shows the divisors of 36 in two groups, one above the other.
- The upper group holds the divisors of 36 from 2 up to its integer square root, 6: they are 2, 3, 4 and 6 (5 does not divide 36). A trial-division loop for 36 tries numbers only in this range, and it stops at the first divisor it finds, 2.
- The lower group holds their partners, the divisors of 36 above 6: 18, 12 and 9. The loop never tries them.
- Arrows join each pair: 2 × 18, 3 × 12 and 4 × 9 all make 36, and 6 × 6 pairs 6 with itself.
Every divisor above the square root comes with a partner below it. So for any number that is not prime, the loop meets a divisor before it passes the square root.
Divisors come in pairs whose product is n, and in each pair the smaller one is at most the square root. Any
number that is not prime therefore has a divisor small enough for the loop to reach. math.isqrt(n) gives the
integer square root: The largest whole number whose square is at most n: math.isqrt(99) is 9, because 81 is at most 99 and 100 is not. It is exact for whole numbers of any size, unlike int(math.sqrt(n))., the largest whole number whose square is at most n:
import math
def is_prime(n):
"""True when the whole number n is a prime."""
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False # a divisor: n is not prime, stop at once
return True
def is_prime_wrong(n):
"""The same with a common mistake: range() stops one short of isqrt(n)."""
if n < 2:
return False
for d in range(2, math.isqrt(n)):
if n % d == 0:
return False
return True
print("primes below 30:", [n for n in range(30) if is_prime(n)])
for n in [0, 1, 2, 4, 9, 15, 25, 97]:
print(f"{n:>2}: is_prime {is_prime(n)!s:<5} is_prime_wrong {is_prime_wrong(n)}")
# Going through a float can be off: one too large for the first number, one too small for the second.
for n in [1_000_000_007**2 - 1, 9_509_733_067_886_049**2]:
print(f"int(math.sqrt(n)) = {int(math.sqrt(n))}, math.isqrt(n) = {math.isqrt(n)}") Output
primes below 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 0: is_prime False is_prime_wrong False 1: is_prime False is_prime_wrong False 2: is_prime True is_prime_wrong True 4: is_prime False is_prime_wrong True 9: is_prime False is_prime_wrong True 15: is_prime False is_prime_wrong True 25: is_prime False is_prime_wrong True 97: is_prime True is_prime_wrong True int(math.sqrt(n)) = 1000000007, math.isqrt(n) = 1000000006 int(math.sqrt(n)) = 9509733067886048, math.isqrt(n) = 9509733067886049
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 primes.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
n < 2is checked first: 0 and 1 are not prime, and the loop would wrongly accept them.- For 2 and 3,
range(2, math.isqrt(n) + 1)is empty, so the loop does not run and the function returnsTrue. - The
+ 1matters.is_prime_wrongstops one divisor short, a common off-by-one error: A loop that runs one time too many or too few, such as range(1, 10) when 1 to 10 was meant. It usually raises no error and gives a wrong result. More in “for loops with range, enumerate and zip” mistake, so it never triesisqrt(n)itself. It calls 4 a prime, because for 4 to 8 its loop is empty; it accepts 9 and 25, the squares of primes, whose only small divisor is the square root; and it accepts 15, whose smallest divisor, 3, isisqrt(15). math.isqrt()works with whole numbers and is always exact.int(math.sqrt(n))goes through a floating-point number, which keeps only 53 bits of precision, and the last two lines show it coming out one too large for one big number and one too small for another. Too small is the dangerous one: for the square of a prime, the loop would stop just before the only divisor that proves it is not prime.
The off-by-one is easiest to see on one number. Step through the wrong loop for 25 and watch the row of its range, with its stop value: The number a range stops before and never gives. range(1, 5) gives 1, 2, 3 and 4, four numbers, 5 − 1, and never 5 itself. More in “for loops with range, enumerate and zip” in the dashed cell at the end:
Program · trial_division_bug.py
import math
n = 25
prime = True
for d in range(2, math.isqrt(n)):
if n % d == 0:
prime = False
break
print(n, "is prime:", prime) Variables
- just taken by the loop
- changed in this step
- passed by the loop
- read next
- where the loop stopped
- the stop value, never given
Printed so far
Nothing printed yet25 is prime: True
Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.
The drawing shows the variables when the program ends, and the program's 12 steps are listed below.
Change the program and run it here. Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Every step as text
- Start. No line has run yet, so there are no variables. Python starts with line 1.
- Line 1.
import mathloadsmath. - Line 3.
n = 25setsnto25. - Line 4.
prime = TruesetsprimetoTrue. - Line 5.
for d in range(2, math.isqrt(n)):gives its first number:dis2. math.isqrt(25) is 5, so this is range(2, 5): it gives 2, 3 and 4, and 5 is its stop value. - Line 6.
n % d == 0is false (nis25anddis2), so Python skips the block underif n % d == 0:. - Line 5.
for d in range(2, math.isqrt(n)):gives the next number:dis3. - Line 6.
n % d == 0is false (nis25anddis3), so Python skips the block underif n % d == 0:. - Line 5.
for d in range(2, math.isqrt(n)):gives the next number:dis4. - Line 6.
n % d == 0is false (nis25anddis4), so Python skips the block underif n % d == 0:. - Line 5.
for d in range(2, math.isqrt(n)):has no number left: a range stops before its stop value,5, so the loop ends. The bug The range has no number left. It stopped before 5, the one divisor that shows 25 = 5 × 5 is not prime, and no error says so. - Line 9.
print(n, "is prime:", prime)prints25 is prime: True. That was the last line, so the program ends. The fix The program calls 25 a prime. Press Edit, write range(2, math.isqrt(n) + 1) on line 5 and run it: the loop then tries 5 and prints 25 is prime: False.
The range gave 2, 3 and 4 and stopped before 5, so the one divisor that proves 25 = 5 × 5 is not prime was never tried, and the loop raised no error.
Version note
math.isqrt() was added in Python 3.8. Older code may use int(n ** 0.5) instead, which goes through a float
too and has the same rounding risk. Python 3.15 also offers isqrt(), gcd() and lcm() in a new module,
math.integer, and keeps the names in math as aliases, so code written for this track’s Python 3.14 still runs;
for new code its documentation recommends the math.integer names.
Checkpoint
Check: Trial division up to isqrt(n)
Euclid’s algorithm keeps the gcd while the numbers shrink
The greatest common divisor (gcd) of two whole numbers is the largest
number that divides both. Euclid’s algorithm finds it with one simple step, repeated: replace the pair (a, b) with
(b, a % b), until b is 0. The plan is short. The invariant is that the pair always has the same gcd as the
original numbers, because a number divides both a and b exactly when it divides both b and a % b; the loop
stops when b is 0, and then the gcd is a. Step through it for the pair 1071 and 462:
Program · euclid_trace.py
a, b = 1071, 462
while b != 0:
a, b = b, a % b
print("gcd:", a) Variables
- changed in this step
Printed so far
Nothing printed yetgcd: 21
Every step was recorded from a run with Python 3.14.8 on macOS 26 arm64.
The drawing shows the variables when the program ends, and the program's 10 steps are listed below.
Change the program and run it here. Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Every step as text
- Start. No line has run yet, so there are no variables. Python starts with line 1.
- Line 1.
a, b = 1071, 462setsato1071and setsbto462. - Line 2.
while b != 0:tests its condition: it is true (bis462), so the body runs. Key point The pair is (1071, 462). A number divides both exactly when it divides 462 and 1071 % 462, which is 147, so the next pair keeps the same gcd. - Line 3.
a, b = b, a % bsetsato462(it was1071) and setsbto147(it was462). - Line 2.
while b != 0:tests its condition: it is true (bis147), so the body runs again (pass 2). (462, 147): 462 % 147 is 21, the next remainder. The numbers shrink fast. - Line 3.
a, b = b, a % bsetsato147(it was462) and setsbto21(it was147). - Line 2.
while b != 0:tests its condition: it is true (bis21), so the body runs again (pass 3). (147, 21): 21 divides 147 exactly, 7 times, so the next remainder is 0. - Line 3.
a, b = b, a % bsetsato21(it was147) and setsbto0(it was21). - Line 2.
while b != 0:tests its condition: it is false (bis0), so the loop ends. b is 0, so the loop stops after three passes. gcd(21, 0) is 21, and by the invariant it is also gcd(1071, 462). - Line 4.
print("gcd:", a)printsgcd: 21. That was the last line, so the program ends.
The pair went from (1071, 462) to (21, 0) in three passes, and its gcd was 21 at every test. This version prints every step for the same pair as a division with its remainder:
import math
def gcd(a, b):
"""Euclid's algorithm: replace (a, b) with (b, a % b) until b is 0."""
while b != 0:
print(f"{a} = {a // b} × {b} + {a % b}")
a, b = b, a % b
return a
print("gcd(1071, 462) =", gcd(1071, 462))
print("math.gcd(1071, 462) =", math.gcd(1071, 462))
print("math.lcm(1071, 462) =", math.lcm(1071, 462)) Output
1071 = 2 × 462 + 147 462 = 3 × 147 + 21 147 = 7 × 21 + 0 gcd(1071, 462) = 21 math.gcd(1071, 462) = 21 math.lcm(1071, 462) = 23562
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 gcd_trace.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Three passes are enough here, because the remainders shrink fast. In real code, use the standard library:
math.gcd() takes any number of arguments (since Python 3.9; before that, exactly two) and math.lcm(), new in
Python 3.9, returns the least common multiple. For two numbers it is their product divided by their gcd: 1071 × 462
÷ 21 = 23,562.
Checkpoint
Check: Euclid's algorithm
Armstrong numbers reuse the digit-sum plan
An Armstrong number: A number equal to the sum of its digits, each raised to the power of the number of digits: 153 = 1³ + 5³ + 3³. Also called a narcissistic number. (also called a narcissistic number) equals the sum of its digits, each raised to the power of the number of digits. The digit loop from the start of the lesson needs one change, the power:
def is_armstrong(n):
"""True when n equals the sum of its digits, each raised to the power of the number of digits."""
power = len(str(n))
total = 0
rest = n
while rest > 0:
total += (rest % 10) ** power
rest //= 10
return total == n
print([n for n in range(100, 1000) if is_armstrong(n)])
print("153 =", " + ".join(f"{d}³" for d in "153"), "=", 1**3 + 5**3 + 3**3) Output
[153, 370, 371, 407] 153 = 1³ + 5³ + 3³ = 153
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 armstrong.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
There are exactly four with three digits. The plan is the same as for the digit sum; only what is added on each pass has changed, which is why it pays to learn the pattern rather than each program.
Written as the four answers, the plan hardly moves. n goes in, and True or False comes out. On each pass one
digit leaves rest and its power joins total. total plus the powers of the digits left in rest stays equal to
the full sum. The loop stops when rest is 0, and the function compares total with n. Press Edit, change the
range to range(1000, 10000) and run it: three Armstrong numbers with four digits appear.
Checkpoint
Check: Reusing the digit plan
Count the work to see how it grows with n
Before you time anything, you can count. For a prime n, trial division tries every divisor it is allowed, so the
count depends only on where the loop stops. This program counts the divisions for the largest prime below 100,
1,000, 10,000, 100,000 and 1,000,000:
import math
def is_prime(n):
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False
return True
def divisions(n, last):
"""How many divisions trial division makes for n, trying the divisors 2, 3, ..., last."""
count = 0
for d in range(2, last + 1):
count += 1
if n % d == 0:
break
return count
print(f"{'prime n':>9} {'up to n - 1':>12} {'up to isqrt(n)':>15}")
for limit in [100, 1_000, 10_000, 100_000, 1_000_000]:
n = limit - 1
while not is_prime(n): # the largest prime below the limit
n -= 1
print(f"{n:>9,} {divisions(n, n - 1):>12,} {divisions(n, math.isqrt(n)):>15,}") Output
prime n up to n - 1 up to isqrt(n)
97 95 8
997 995 30
9,973 9,971 98
99,991 99,989 315
999,983 999,981 998
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 count_divisions.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each time the number grows ten times, the loop up to n - 1 makes ten times as many divisions, but the loop up to
isqrt(n) only about three times as many, since the square root of 10 is about 3.16. The usual shorthand for this is
big-O notation: A way to say how the work of an algorithm grows with the size of its input: O(n) grows at most in proportion to n, O(√n) with the square root of n.: the first loop is O(n) and the second O(√n), meaning the work grows at
most in proportion to n and to the square root of n.
| Operation | Time | Extra space |
|---|---|---|
| is_prime(n), divisors up to n - 1 | O(n) | O(1) |
| is_prime(n), divisors up to isqrt(n) | O(√n) | O(1) |
| digit_sum(n) for a number of d digits | O(d) | O(1) |
The table counts each division as one step, which is fair for numbers of everyday size. Python’s integers have unlimited precision, though, and dividing a number with thousands of digits takes longer than dividing a small one, so for huge numbers the time grows faster than the count of steps.
Counts predict, and a clock confirms. This program times both versions on 999,983, the largest prime below a million:
import math
import time
def is_prime_slow(n):
"""Trial division with every divisor up to n - 1."""
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True
def is_prime(n):
"""Trial division with divisors up to isqrt(n) only."""
if n < 2:
return False
for d in range(2, math.isqrt(n) + 1):
if n % d == 0:
return False
return True
for check in [is_prime_slow, is_prime]:
start = time.perf_counter()
answer = check(999_983)
milliseconds = (time.perf_counter() - start) * 1000
print(f"{check.__name__}(999_983) = {answer} in {milliseconds:.3f} ms") Output
is_prime_slow(999_983) = True in 33.358 ms is_prime(999_983) = True in 0.042 ms
This output changes from run to run: it measures time, which differs from one run to the next and from one computer to another; the computer of this run is named below the output.
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 timing.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The recorded times come from the computer named under the output, and yours will differ, in the browser more so, because Python runs more slowly there. What does not change is the shape: a thousand times fewer divisions makes the second version hundreds of times faster. Counting the work first tells you whether a loop will be fast enough before you wait for it.
Checkpoint
Check: How the work grows with n
Practise: list primes with a sieve
Write the clearest loop you can while you are solving a problem, test it on small inputs whose answers you know,
and only then make it faster or shorter. Keep the tests, so that each change can be checked against them. For real
programs, prefer the standard library: math.isqrt(), math.gcd() and math.lcm() work exactly with whole
numbers of any size. And when you need many primes rather than one, a different algorithm, the sieve of
Eratosthenes in this lesson’s exercise, does far less work than calling is_prime() again and again.
The exercise asks for two functions: primes_up_to(n), which crosses out the multiples of each prime in a list of
booleans, and nth_prime(k), which grows its limit until the list holds k primes. Its sample tests include the
78,498 primes up to one million and the 100,000th prime, 1,299,709, which lies beyond that million.
Exercise · Medium · Python
List primes with a sieve and find the k-th prime
Trial division checks one number at a time. To list every prime up to n, the sieve of Eratosthenes is much faster: start with all the numbers from 2 to n marked as possible primes; take the smallest one still marked, which is a prime, and cross out all its larger multiples (for 2: 4, 6, 8 and so on); repeat with the next number still marked. The numbers never crossed out are the primes.
Write two functions:
primes_up_to(n)returns a list of every prime from 2 to n, n included when it is prime, in increasing order, using a sieve. For any n below 2 it returns an empty list.primes_up_to(10)is[2, 3, 5, 7].nth_prime(k)returns the k-th prime, counting from 1:nth_prime(1)is 2 andnth_prime(6)is 13. For k below 1 it raisesValueError.
The tests include primes_up_to(1_000_000), which has 78,498 primes, and nth_prime(100_000), which is larger than one million, so the sieve has to finish in a few seconds in your browser, and nth_prime() must not stop at a fixed limit.
Starter code · sieve.py
import math
def primes_up_to(n):
"""Return the primes from 2 to n, in order, found with a sieve of Eratosthenes."""
return []
def nth_prime(k):
"""Return the k-th prime number, counting from 1 (nth_prime(1) is 2)."""
return 2 The sample tests · test_sieve.py
from sieve import nth_prime, primes_up_to
def test_small_limits():
"""lists the primes up to small limits, the limit included"""
assert primes_up_to(10) == [2, 3, 5, 7]
assert primes_up_to(2) == [2]
assert primes_up_to(13) == [2, 3, 5, 7, 11, 13]
assert primes_up_to(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def test_no_primes():
"""returns an empty list below 2"""
assert primes_up_to(1) == []
assert primes_up_to(0) == []
assert primes_up_to(-5) == []
def test_squares_are_not_prime():
"""crosses out the squares of primes, such as 25 and 49"""
primes = primes_up_to(100)
assert 25 not in primes
assert 49 not in primes
assert len(primes) == 25
def test_one_million():
"""finds the 78,498 primes up to one million"""
primes = primes_up_to(1_000_000)
assert len(primes) == 78_498
assert primes[-1] == 999_983
def test_nth_prime():
"""counts the primes from 1"""
assert nth_prime(1) == 2
assert nth_prime(6) == 13
assert nth_prime(1000) == 7919
assert nth_prime(100_000) == 1_299_709
def test_nth_prime_rejects_k_below_1():
"""raises ValueError for k below 1"""
try:
nth_prime(0)
except ValueError:
return
assert False, "nth_prime(0) should raise ValueError" A hint
Keep a list of n + 1 booleans, is_prime = [True] * (n + 1), where position i says whether i may still be prime, and set positions 0 and 1 to False. For each p from 2 to math.isqrt(n) that is still True, set every multiple of p from p * p to n to False: range(p * p, n + 1, p) walks through them. For nth_prime(k), sieve up to a limit, and while the list holds fewer than k primes, double the limit and sieve again.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Finally, the questions on planning, primes, the gcd, digits and growth. Each answer is marked at once with its reason, and a question you miss comes back once at the end of the session:
Practice that adapts to you
Practise this lesson
14 questions about 5 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Interview questions
Fresher · Why does trial division only need to try divisors up to the square root of n?
If n is not prime, it can be written as a × b with both factors above 1. The smaller of the two is at most
√n, because if both were larger, their product would be larger than n. So every number that is not prime has a
divisor no larger than its square root, and a loop that tries 2 up to math.isqrt(n) finds one; for 36 it meets 2
long before 2’s partner, 18. If the loop finds none, n is prime. math.isqrt(n) gives the bound exactly for whole
numbers of any size, and the range needs + 1, because range() stops before its stop value:
range(2, math.isqrt(n)) misses the square root itself and calls 25 and 49 prime. The bound turns about n
divisions into about √n: 998 instead of 999,981 for the prime 999,983.
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
Fresher to mid
A coupon service calls a 12-digit code lucky when its number is prime. The check uses trial division with every divisor up to n − 1, and it times out on the first batch of 5,000 codes. Estimate why, fix it, and say what you would change if the batch grew to 5 million codes.
-
Fresher to mid
A billing module finds the gcd of two amounts with a loop that subtracts the smaller from the larger until they are equal. It is correct, yet gcd(10**12, 1) seems never to finish. Explain why, rewrite it, and use an invariant to argue that your loop is correct and always stops.
Key takeaways
- Plan a loop in words first: what goes in and comes out, what changes on each pass, what stays true (the invariant), and when it stops.
- Test the smallest inputs and the ones the plan excludes, such as 0, 1 and negative numbers.
- Trial division needs divisors only up to
math.isqrt(n), and stops at the first one that divides;range()’s stop value needs the+ 1. - Euclid’s algorithm repeats
a, b = b, a % buntilbis 0; real code callsmath.gcd()andmath.lcm(). - Count operations to see how work grows: up to n is O(n), up to √n is O(√n), and timing confirms what the count predicts.
Terms in this lesson
- Armstrong number
- A number equal to the sum of its digits, each raised to the power of the number of digits: 153 = 1³ + 5³ + 3³. Also called a narcissistic number.
- big-O notation
- A way to say how the work of an algorithm grows with the size of its input: O(n) grows at most in proportion to n, O(√n) with the square root of n.
- greatest common divisor (gcd)
- The largest whole number that divides two numbers exactly: gcd(1071, 462) is 21. Euclid's algorithm finds it, and math.gcd() computes it.
- integer square root
- The largest whole number whose square is at most n: math.isqrt(99) is 9, because 81 is at most 99 and 100 is not. It is exact for whole numbers of any size, unlike int(math.sqrt(n)).
- invariant
- A statement about a loop's variables that is true at the start of every pass, such as total plus the digit sum of what is left in n equals the answer. When the loop stops, it says why the result is right.
- trial division
- Testing whether n is prime by trying the possible divisors one by one, from 2 up to the integer square root of n, and stopping at the first one that divides n exactly.
References
- math: isqrt(), gcd() and lcm() (Python Software Foundation)
- math.integer: integer functions (Python 3.15) (Python Software Foundation)
- Numeric types: integer division and remainder (Python Software Foundation)
- The Python Tutorial: floating-point arithmetic, issues and limitations (Python Software Foundation)
- time.perf_counter() (Python Software Foundation)
- The Python Tutorial: more control flow tools (Python Software Foundation)
- Euclid's algorithm (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- Sieve of Eratosthenes (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- Big-O notation (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology (NIST))
- A005188: Armstrong (narcissistic) numbers (The OEIS Foundation)
- A003618: Largest n-digit prime (The OEIS Foundation)
- A006880: Number of primes below 10^n (The OEIS Foundation)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress