Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Type a name or a two-letter code. Use the up and down arrow keys to move through the countries, Enter to choose one and Escape to close.

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.

  • Beginner
  • 20 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free lesson, Pro answers: 20 minutes
Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

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:

  1. What goes in and what comes out? A whole number n that is 0 or more; the sum of its digits.
  2. What changes on each pass? One digit moves out of n and into a running total: n % 10 is the last digit and n //= 10 drops it.
  3. What stays true at the start of every pass? total plus the digit sum of what is left in n always 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..
  4. When does it stop? When n is 0, no digits are left, so by the invariant total is 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:

Interactive · line by line The digit-sum loop for 9475, pass by pass Each step runs one line. At every loop test, add total to the digits left in n: the result is 25 every time.

Program · digit_sum_trace.py

n = 9475
total = 0
while n > 0:
    total += n % 10
    n //= 10
print(total)

Variables

After line 6: n is 0; total is 25.n0total25
  • changed in this step

Printed so far

25

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.

Line run 6
Next line end
Loop pass –
Every step as text
  1. Start. No line has run yet, so there are no variables. Python starts with line 1.
  2. Line 1. n = 9475 sets n to 9475.
  3. Line 2. total = 0 sets total to 0.
  4. Line 3. while n > 0: tests its condition: it is true (n is 9475), 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.
  5. Line 4. total += n % 10 changes total from 0 to 5.
  6. Line 5. n //= 10 changes n from 9475 to 947.
  7. Line 3. while n > 0: tests its condition: it is true (n is 947), so the body runs again (pass 2). One digit, 5, has moved from n to total: 5 + (9 + 4 + 7) = 25 again.
  8. Line 4. total += n % 10 changes total from 5 to 12.
  9. Line 5. n //= 10 changes n from 947 to 94.
  10. Line 3. while n > 0: tests its condition: it is true (n is 94), 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.
  11. Line 4. total += n % 10 changes total from 12 to 16.
  12. Line 5. n //= 10 changes n from 94 to 9.
  13. Line 3. while n > 0: tests its condition: it is true (n is 9), so the body runs again (pass 4). 16 + 9 = 25, with one digit left in n.
  14. Line 4. total += n % 10 changes total from 16 to 25.
  15. Line 5. n //= 10 changes n from 9 to 0.
  16. Line 3. while n > 0: tests its condition: it is false (n is 0), 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.
  17. Line 6. print(total) prints 25. 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:

A digit sum, planned and traced Python · digit_sum.py
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

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

  1. Question 1 of 2 The digit-sum loop runs while n > 0:. When it stops, why is total the answer?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: n is 0, so no digits are left, and the invariant says total plus the digits left is the answer

    At the top of every pass, total plus the digit sum of what is left in n equals the answer. The loop stops when n is 0, and then the digit sum of what is left is 0, so total is the answer.

  2. Question 2 of 2 digit_sum(-25) returns 0. Which part of the plan explains it?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: What goes in. The plan said n is 0 or more, and for -25 the test n > 0 is False at once, so the loop never runs

    An edge case the plan does not expect gives a wrong answer without an error. Checking the smallest inputs and the excluded ones, 0 and -25 here, finds it.

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:

The divisors 2, 3, 4 and 6 of 36, up to its square root, each linked to its partner 18, 12, 9 or 6, so no larger divisor needs a try.Divisors up to isqrt(36) = 6Partners above 6: never tried2346181292 × 183 × 124 × 96 × 6

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:

Trial division up to isqrt(n) Python · primes.py
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

  • n < 2 is 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 returns True.
  • The + 1 matters. is_prime_wrong stops 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 tries isqrt(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, is isqrt(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:

Interactive · line by line Trial division that stops one divisor short The loop should try every divisor up to isqrt(25), which is 5. Watch the row of the range and the stop value it never gives.

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

After line 9: n is 25; prime is True; d is 4.n25primeTrued4
  • 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

25 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.

Line run 9
Next line end
Loop pass –
Every step as text
  1. Start. No line has run yet, so there are no variables. Python starts with line 1.
  2. Line 1. import math loads math.
  3. Line 3. n = 25 sets n to 25.
  4. Line 4. prime = True sets prime to True.
  5. Line 5. for d in range(2, math.isqrt(n)): gives its first number: d is 2. math.isqrt(25) is 5, so this is range(2, 5): it gives 2, 3 and 4, and 5 is its stop value.
  6. Line 6. n % d == 0 is false (n is 25 and d is 2), so Python skips the block under if n % d == 0:.
  7. Line 5. for d in range(2, math.isqrt(n)): gives the next number: d is 3.
  8. Line 6. n % d == 0 is false (n is 25 and d is 3), so Python skips the block under if n % d == 0:.
  9. Line 5. for d in range(2, math.isqrt(n)): gives the next number: d is 4.
  10. Line 6. n % d == 0 is false (n is 25 and d is 4), so Python skips the block under if n % d == 0:.
  11. 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.
  12. Line 9. print(n, "is prime:", prime) prints 25 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)

  1. Question 1 of 2 What does math.isqrt(99) return?

    Type a number.

    A hint

    The largest whole number whose square is at most 99.

    Show the answer: Question 1 of 2

    Answer: 9

    9 × 9 is 81, which is at most 99, while 10 × 10 is 100, which is more. So isqrt(99) is 9, and trial division for 99 tries the divisors 2 to 9.

  2. Question 2 of 2 How many divisions does is_prime(91) from primes.py make before it returns False?

    Type a number.

    A hint

    91 is 7 × 13, and the loop stops at the first divisor it finds.

    Show the answer: Question 2 of 2

    Answer: 6 divisions

    isqrt(91) is 9, so the loop may try 2 to 9. It tries 2, 3, 4, 5, 6 and 7, and 91 % 7 is 0, so it returns False after six divisions, without trying 8 or 9.

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:

Interactive · line by line Euclid's algorithm on 1071 and 462 Each pass replaces the pair (a, b) with (b, a % b). At every loop test the pair has the same gcd as the first pair, 21.

Program · euclid_trace.py

a, b = 1071, 462
while b != 0:
    a, b = b, a % b
print("gcd:", a)

Variables

After line 4: a is 21; b is 0.a21b0
  • changed in this step

Printed so far

gcd: 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.

Line run 4
Next line end
Loop pass –
Every step as text
  1. Start. No line has run yet, so there are no variables. Python starts with line 1.
  2. Line 1. a, b = 1071, 462 sets a to 1071 and sets b to 462.
  3. Line 2. while b != 0: tests its condition: it is true (b is 462), 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.
  4. Line 3. a, b = b, a % b sets a to 462 (it was 1071) and sets b to 147 (it was 462).
  5. Line 2. while b != 0: tests its condition: it is true (b is 147), so the body runs again (pass 2). (462, 147): 462 % 147 is 21, the next remainder. The numbers shrink fast.
  6. Line 3. a, b = b, a % b sets a to 147 (it was 462) and sets b to 21 (it was 147).
  7. Line 2. while b != 0: tests its condition: it is true (b is 21), so the body runs again (pass 3). (147, 21): 21 divides 147 exactly, 7 times, so the next remainder is 0.
  8. Line 3. a, b = b, a % b sets a to 21 (it was 147) and sets b to 0 (it was 21).
  9. Line 2. while b != 0: tests its condition: it is false (b is 0), 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).
  10. Line 4. print("gcd:", a) prints gcd: 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:

Euclid's algorithm, traced Python · gcd_trace.py
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

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.

LCM & HCF (GCD) Calculator Check your answers for any set of numbers, with the steps of Euclid's algorithm.

Checkpoint

Check: Euclid's algorithm

  1. Question 1 of 2 Euclid's loop starts with a, b = 1071, 462. What is the pair after the first pass?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: (462, 147)

    a, b = b, a % b gives (462, 1071 % 462) = (462, 147). Both pairs have the same greatest common divisor, 21.

  2. Question 2 of 2 What does Euclid's algorithm return for the pair (84, 36)?

    Type a number.

    A hint

    Replace (a, b) with (b, a % b) until b is 0.

    Show the answer: Question 2 of 2

    Answer: 12

    84 % 36 is 12, so the pair becomes (36, 12); 36 % 12 is 0, so it becomes (12, 0), and the loop stops with a = 12.

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:

The three-digit Armstrong numbers Python · armstrong.py
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

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

  1. Question 1 of 2 Is 371 an Armstrong number?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: Yes, 3³ + 7³ + 1³ = 27 + 343 + 1 = 371

    For a number of three digits, cube each digit and add: 27 + 343 + 1 = 371, the number itself, so 371 is an Armstrong number.

  2. Question 2 of 2 What is the one change from the digit-sum loop to the Armstrong loop?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: Each digit is raised to the power of the number of digits before it is added

    The plan stays the same: one digit leaves the number on each pass, and the loop ends when none are left. Only what is added changes, from the digit to the digit to a power.

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:

Counting divisions instead of timing them Python · count_divisions.py
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

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.

The loops of this lesson
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:

Timing the two versions Python · timing.py
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

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

  1. Question 1 of 2 From the prime 99,991 to the prime 999,983, the divisions of the loop up to isqrt(n) go from 315 to 998. About how many times as many is that?

    Type a number.

    A hint

    Divide 998 by 315.

    Show the answer: Question 1 of 2

    Answer: 3.2 times (anything from 3 to 3.4 counts)

    998 ÷ 315 is about 3.17, close to the square root of 10, about 3.16: n grew ten times, and the work grew with its square root.

  2. Question 2 of 2 Which loop of this lesson is O(n)?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: Trial division with every divisor up to n − 1

    Big-O says how the work grows: up to n − 1 the divisions grow like n, up to isqrt(n) like √n, and a digit loop like the number of digits.

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 and nth_prime(6) is 13. For k below 1 it raises ValueError.

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.

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.

Prime Number Checker & Generator Check whether a number is prime, or list the primes in a range, to test your own functions.

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.

  1. Question 1 of 14 Which of these is the invariant of the digit-sum loop?

    Choose one answer.

    Show the answer: Question 1 of 14

    Answer: total plus the digit sum of what is left in n equals the answer

    An invariant connects what the loop has done with what is left to do. Here the digits move from n into total, so their sum stays the answer on every pass.

  2. Question 2 of 14 digit_sum() is the function from digit_sum.py. What does this print?

    Read the code, then choose one answer.

    print(digit_sum(-25))
    Show the answer: Question 2 of 14

    Answer: 0

    The loop runs only while n > 0, and -25 is not, so the body never runs and the function returns the 0 it started with. The plan assumed n is 0 or more; a function meant for negative numbers too should work with abs(n), and one that is not should raise an error for them.

  3. Question 3 of 14 You plan a loop that counts the digits of a whole number n that is 0 or more, so 9475 gives 4. Which loop is right for every such n?

    Choose one answer.

    A hint

    How many digits does 0 have?

    Show the answer: Question 3 of 14

    Answer: count = 1, then while n >= 10: n //= 10 and count += 1

    Plan the edge case first: 0 has one digit. Starting the count at 1 and dropping digits while n has two or more gives the right answer for 0, 7 and 9475 alike.

  4. Question 4 of 14 Why may trial division stop at the integer square root of n?

    Choose one answer.

    Show the answer: Question 4 of 14

    Answer: Because if n = a × b with a ≤ b, then a is at most the square root of n, so every pair has a member the loop tries

    Divisors come in pairs whose product is n, and in each pair the smaller one is at most the square root. So every number that is not prime has a divisor within reach of the loop, and stopping there misses nothing.

  5. Question 5 of 14 How many divisions does is_prime(97) from primes.py make before it returns True?

    Type a number.

    Show the answer: Question 5 of 14

    Answer: 8 divisions

    math.isqrt(97) is 9, so the loop tries the divisors 2, 3, 4, 5, 6, 7, 8 and 9: eight divisions, none of them exact, and then it returns True. Trying every divisor up to 96 would take 95.

  6. Question 6 of 14 is_prime_wrong() loops over range(2, math.isqrt(n)). Which of these numbers does it wrongly call prime?

    Choose every answer that is right.

    Show the answer: Question 6 of 14

    Answer:

    • 49
    • 8

    Without the + 1 the loop never tries isqrt(n) itself. Numbers whose only small divisor is their square root, such as 49, and numbers whose range becomes empty, such as 8, are called prime by mistake.

  7. Question 7 of 14 What stays true at the top of every pass of the loop in Euclid's algorithm, a, b = b, a % b?

    Choose one answer.

    Show the answer: Question 7 of 14

    Answer: The greatest common divisor of a and b is that of the two original numbers

    A number divides both a and b exactly when it divides both b and a % b, so each step keeps the same greatest common divisor. When b reaches 0, the answer is a, because gcd(a, 0) is a.

  8. Question 8 of 14 The greatest common divisor of 252 and 105 is 21. What is their least common multiple?

    Type a number.

    A hint

    For two numbers, divide their product by their gcd.

    Show the answer: Question 8 of 14

    Answer: 1260

    252 × 105 is 26,460, and 26,460 ÷ 21 is 1,260. math.lcm(252, 105) returns the same.

  9. Question 9 of 14 Euclid's loop is called with the smaller number first, a, b = 462, 1071. What happens?

    Choose one answer.

    Show the answer: Question 9 of 14

    Answer: The first pass swaps them, because 462 % 1071 is 462, and the loop then goes on as before, one pass longer

    The remainder of a smaller number divided by a larger one is the smaller number itself, so the first pass only swaps the pair. The order of the arguments costs one pass and changes nothing else.

  10. Question 10 of 14 What does armstrong.py print?

    What does this program print? Choose one answer.

    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)
    Show the answer: Question 10 of 14

    Answer: it prints

    [153, 370, 371, 407]
    153 = 1³ + 5³ + 3³ = 153

    The program checks every number from 100 to 999, so 1 is not in the range, and four three-digit numbers equal the sum of the cubes of their digits: 153, 370, 371 and 407.

  11. Question 11 of 14 Is 9474 an Armstrong number?

    Choose one answer.

    A hint

    It has four digits, so each digit is raised to the fourth power.

    Show the answer: Question 11 of 14

    Answer: Yes, 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474

    is_armstrong() raises each digit to len(str(n)), so for 9474 it adds four fourth powers: 6561 + 256 + 2401 + 256 = 9474. Change the range in armstrong.py to 1000 to 10000 to list all three four-digit ones.

  12. Question 12 of 14 What does it mean that trial division up to isqrt(n) is O(√n)?

    Choose one answer.

    Show the answer: Question 12 of 14

    Answer: Its work grows at most in proportion to the square root of n

    Big-O notation describes how the work grows with the input. The isqrt loop tries at most about √n divisors, so its work grows with √n, while the loop up to n − 1 grows with n.

  13. Question 13 of 14 For a prime near one million, trial division up to math.isqrt(n) makes about 1,000 divisions. About how many does it make for a prime near 100 million, a hundred times larger?

    Type a number.

    Show the answer: Question 13 of 14

    Answer: 10000 divisions (anything from 9500 to 10500 counts)

    The work grows with the square root of n. A hundred times larger n has a square root ten times larger, so about 10,000 divisions: the integer square root of 100,000,000 is exactly 10,000. Trial division up to n - 1 would need a hundred times more divisions instead, about 100 million.

  14. Question 14 of 14 n grows a million times, from about 10⁶ to about 10¹². About how many times as many divisions does trial division up to isqrt(n) make for a prime of that size?

    Type a number.

    A hint

    Take the square root of the factor by which n grows.

    Show the answer: Question 14 of 14

    Answer: 1000 times (anything from 900 to 1100 counts)

    √(10⁶) is 10³ and √(10¹²) is 10⁶, so the divisions grow from about a thousand to about a million: a thousand times as many. The loop up to n − 1 would make a million times as many, about 10¹² for each prime.

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.

  1. 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.

    Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups

  2. 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.

    Model answer, Pro. First step and follow-ups

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 % b until b is 0; real code calls math.gcd() and math.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

Related tools

Report a problem with this lesson

Quick answers and tool search

Type to search tools or to get a quick answer, for example 18% of 2500. Use the up and down arrow keys to move through the results, Enter to choose, and Escape to close.