Session 13 Primes in Range

Published

August 4, 2026

We reviewed the single dice roll and two dice roll simulation programs and saw how the values can be plotted using matplotlib. We then discussed the problem of finding prime numbers in a range and how to break it down into smaller parts.

Problem and goal

We want a program that takes a start and end of a range, for example 10 to 50, and finds all the prime numbers in that range.

For example:

  • Input: start = 10, end = 20
  • Output: 11, 13, 17, 19

So the problem naturally breaks into two parts:

  • How do we check whether one number is prime?
  • How do we repeat that check for every number in the range?

Math behind the problem

A number n greater than 1 is prime if its only positive divisors are 1 and n itself.

This means that if n is not prime, then there must be some number d between 2 and n - 1 that divides n exactly.

A useful mathematical idea makes the work smaller:

  • To test whether n is prime, it is enough to check divisors only up to sqrt(n).

Why?

  • If n = a * b, and both a and b are larger than sqrt(n), then a * b would be greater than n, which is impossible.
  • So if n has a factor, at least one factor must be less than or equal to sqrt(n).

Therefore, to test if a number is prime:

  1. If n <= 1, it is not prime.
  2. Compute sqrt(n).
  3. Try dividing n by every integer from 2 up to sqrt(n).
  4. If any divisor works exactly, n is not prime.
  5. If no divisor works, n is prime.

What the program needs to do

For a range from start to end:

  1. Start with an empty list of primes.
  2. For each number n in the range:
    • Check whether n is prime.
    • If it is prime, add it to the list.
  3. At the end, output the list of primes.

This suggests two functions:

  • is_prime(n) to test one number.
  • primes_in_range(start, end) to collect all the primes in the interval.

Pseudocode

Helper function: is_prime

FUNCTION is_prime(n):

    IF n <= 1:
        RETURN False

    SET limit = floor(sqrt(n))

    FOR d from 2 to limit:
        IF n mod d == 0:
            RETURN False

    RETURN True

Main function: primes_in_range

FUNCTION primes_in_range(start, end):

    CREATE empty list primes

    FOR n from start to end:
        IF is_prime(n):
            append n to primes

    RETURN primes

Python code

Helper function: is_prime

import math

def is_prime(n):
    """Return True if n is prime, False otherwise."""
    if n <= 1:
        return False

    limit = int(math.sqrt(n))

    for d in range(2, limit + 1):
        if n % d == 0:
            return False

    return True

Main function: primes_in_range

def primes_in_range(start, end):
    """Return a list of all prime numbers between start and end (inclusive)."""
    primes = []

    for n in range(start, end + 1):
        if is_prime(n):
            primes.append(n)

    return primes

Example usage

start = 10
end = 50
primes = primes_in_range(start, end)
print("Prime numbers between", start, "and", end, "are:")
print(primes)

What to note in the pseudocode

  • The problem is split into two functions.
  • is_prime(n) does only one job: decide whether one number is prime.
  • primes_in_range(start, end) repeats that test for every number in the interval.
  • The mathematical idea of checking only up to sqrt(n) reduces the amount of work.
  • The pseudocode uses loops, conditionals, and a list to organize the solution.

What to note in the Python code

  • import math is needed for math.sqrt(n).
  • int(math.sqrt(n)) gives the whole-number limit for divisor checking.
  • range(2, limit + 1) checks all possible divisors from 2 up to the limit.
  • n % d == 0 tests whether d divides n exactly.
  • primes = [] creates an empty list, and primes.append(n) adds a prime number to it.
  • The Python code follows the same structure as the pseudocode, which is the main habit to practice.