SyntaxPilot
Courses/Python Coding Questions/Lesson 2
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 2 of 30

Number questions II

prime check (why up to √n, math.isqrt)all primes up to n (Sieve of Eratosthenes)Armstrong number; timing with time.perf_counter

These are the notes for Python Coding Questions, episode 2. Three questions from almost every placement test: is n prime?, all primes up to n and Armstrong numbers. This time speed matters: the same answer can take seconds or a millisecond, and the difference is one idea: divisors come in pairs.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings depend on the machine, so yours will differ; what matters is the ratio between the slow and the fast version.

Words you need first

  • A divisor of n is a number d that divides n exactly: n % d == 0. The divisors of 12 are 1, 2, 3, 4, 6, 12.
  • A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, ... By definition, 0 and 1 are not prime, and 2 is the only even prime.
  • A composite number is a whole number > 1 that is not prime: 4, 6, 9, 12, ...
  • time.perf_counter() is a stopwatch: read it before and after, and subtract, to get the seconds in between.
  • Python lets you write _ inside numbers for readability: 1_000_000 is one million.

Q1: Is n prime?

Problem. Given an integer n, return True if it is prime.

Input Output
2 True
7 True
9 False (3 × 3)
1 False (by definition)
0 False
97 True

Think out loud

Try divisors; if any divides n, it's not prime. Edge cases: 0, 1, 2, perfect squares (9, 25, 49) and a huge prime (the slowest case, because the loop never finds a divisor and has to try everything).

The obvious attempt: try every divisor

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

for n in [2, 7, 9, 1, 0]:
    print(n, is_prime(n))

Output:

2 True
7 True
9 False
1 True
0 True

Why 1 and 0 are wrong: range(2, 1) and range(2, 0) are empty, so the loop never runs and the function falls through to return True. An empty loop proves nothing. Fix: if n < 2: return False first.

It's correct now, but slow

import time

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

start = time.perf_counter()
print(is_prime(100_000_007))
print(f"{time.perf_counter() - start:.2f} seconds")

Output (one run; the time depends on the machine):

True
2.73 seconds

For a prime, the loop tries almost 100 million divisors: O(n) time. A 10-digit prime would take ten times longer.

Why √n is enough: divisors come in pairs

Arrange 36 chairs in equal rows: 2 × 18, 3 × 12, 4 × 9, 6 × 6. Every divisor a has a partner b = n // a, with a × b = n. After the 6 × 6 square the pairs just flip (9 × 4 is 4 × 9 again), and 6 = √36.

So if n has any divisor other than 1 and n, the smaller one of its pair is at most √n. Check up to √n and you have checked everything. For 100,000,007 that is about 10,000 checks instead of 100 million.

The off-by-one trap

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5)):
        if n % i == 0:
            return False
    return True

for n in [2, 7, 9, 1, 25, 49]:
    print(n, is_prime(n))

Output:

2 True
7 True
9 True
1 False
25 True
49 True

For 25, int(25 ** 0.5) is 5, and range(2, 5) is 2, 3, 4: range stops before its end, so it never tries 5, the one divisor that matters. Every perfect square of a prime (4, 9, 25, 49, 121, ...) is reported as prime.

The fix: math.isqrt(n) + 1

import math, time

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

for n in [2, 7, 9, 1, 25, 49, 97]:
    print(n, is_prime(n))
start = time.perf_counter()
print(is_prime(1_000_000_007))
print(f"{time.perf_counter() - start:.4f} seconds")

Output:

2 True
7 True
9 False
1 False
25 False
49 False
97 True
True
0.0009 seconds

math.isqrt(n) is the integer square root: the largest whole number whose square is ≤ n, computed exactly with integers. n ** 0.5 goes through a float, which only keeps about 16 significant digits, so for big numbers it can be off by one:

import math
for k in [10**8 + 7, 10**15 + 37]:
    n = k * k - 1
    print(int(n ** 0.5), math.isqrt(n))

Output:

100000007 100000006
1000000000000037 1000000000000036

The true answer is k − 1 (because k² − 1 < k²); the float version is one too high.

Complexity

O(√n) time, O(1) space. A 10-digit prime needs about 31,623 checks instead of a billion.

Q2: All primes up to n

Problem. Given n, return every prime p with p <= n.

Input Output
13 [2, 3, 5, 7, 11, 13]
1_000_000 78498 primes
1 []

The obvious attempt: test every number

import math, time

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

def primes_up_to(n):
    return [k for k in range(2, n) if is_prime(k)]

print(primes_up_to(13))
start = time.perf_counter()
print(len(primes_up_to(1_000_000)), "primes")
print(f"{time.perf_counter() - start:.2f} seconds")

Output:

[2, 3, 5, 7, 11]
78498 primes
1.83 seconds

Two problems: 13 is missing (range(2, n) stops before n), and it is slow: each of a million numbers gets its own √k loop, about n × √n steps, repeating the same divisions again and again.

The Sieve of Eratosthenes

A teacher writes roll numbers 2 to 30 on the board and assumes they are all prime. 2 is the first, so it's prime: cross out every 2nd number after it (4, 6, 8, ...). The next number not crossed out, 3, is prime: cross out its multiples, starting at 9 = 3 × 3 (6 was already crossed out by 2). Then 5, starting at 25. Stop at √30 ≈ 5: what is left is prime. This method is over 2,000 years old and is named after the Greek mathematician Eratosthenes.

import math, time

def sieve(n):
    is_prime = [True] * (n + 1)          # index = the number
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(n) + 1):
        if is_prime[i]:
            for multiple in range(i * i, n + 1, i):
                is_prime[multiple] = False
    return [k for k in range(n + 1) if is_prime[k]]

print(sieve(13))
start = time.perf_counter()
print(len(sieve(1_000_000)), "primes")
print(f"{time.perf_counter() - start:.2f} seconds")

Output:

[2, 3, 5, 7, 11, 13]
78498 primes
0.05 seconds

Why start at i * i? Every smaller multiple i × j with j < i was already crossed out when we handled j (or one of its prime factors). Why stop the outer loop at √n? A composite number ≤ n always has a prime factor ≤ √n, so it is already crossed out by then.

Complexity

Method Time Extra space
is_prime for every k about O(n √n) O(1) (plus the result)
Sieve of Eratosthenes O(n log log n), almost O(n) O(n) for the list of booleans

Use the sieve when you need many primes (all primes up to n, many prime checks on numbers up to n); use the √n check for one number, or for numbers too big for a list.

Q3: Armstrong number

Problem. A number with k digits is an Armstrong number (also called a narcissistic number) if the sum of its digits, each raised to the power k, equals the number.

Input Working Output
153 1³ + 5³ + 3³ = 1 + 125 + 27 = 153 True
370 3³ + 7³ + 0³ = 27 + 343 + 0 = 370 True
123 1 + 8 + 27 = 36 False
9474 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 True
7 7¹ = 7 True

The obvious attempt: cube every digit

def is_armstrong(n):
    total = 0
    m = n
    while m > 0:
        total += (m % 10) ** 3
        m //= 10
    return total == n

for n in [153, 370, 123, 9474]:
    print(n, is_armstrong(n))

Output:

153 True
370 True
123 False
9474 False

m is a copy, so n isn't destroyed (the episode 1 lesson). m //= 10 is short for m = m // 10. But 9474 is wrong: the power was hard-coded to 3, and 9474 has 4 digits.

The fix: the power is the number of digits

def is_armstrong(n):
    k = len(str(n))               # number of digits
    total = 0
    m = n
    while m > 0:
        total += (m % 10) ** k
        m //= 10
    return total == n

for n in [153, 370, 123, 9474, 0, 7]:
    print(n, is_armstrong(n))
print([n for n in range(100_000) if is_armstrong(n)])

Output:

153 True
370 True
123 False
9474 True
0 True
7 True
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084]

Pythonic version:

def is_armstrong(n):
    digits = str(n)
    k = len(digits)
    return n == sum(int(ch) ** k for ch in digits)

print([n for n in range(1000) if is_armstrong(n)])

Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]

Complexity: O(d) time per number (d digits); O(d) space for the string, or O(1) if you count the digits with the digit loop instead.

Common mistakes (and what you really see)

Mistake What you see Why Fix
no n < 2 check 1 True, 0 True the empty loop falls through to True if n < 2: return False
range(2, n) for one big prime seconds for one number O(n) divisors stop at √n
range(2, int(n ** 0.5)) 9 True, 25 True, 49 True range stops before its end range(2, math.isqrt(n) + 1)
int(n ** 0.5) for huge n one too high for some n floats keep ~16 digits math.isqrt(n)
[k for k in range(2, n) ...] 13 missing from primes up to 13 range leaves out n range(n + 1)
is_prime(k) for every k up to n seconds for n = 1,000,000 each number tested separately the sieve
(digit) ** 3 always 9474 False the power is the digit count k = len(str(n))
i % 2 == 0 → "not prime" 2 reported as not prime 2 is even and prime handle 2 first

Mini project: prime factorisation

Every whole number > 1 is a product of primes in exactly one way (the fundamental theorem of arithmetic): 360 = 2 × 2 × 2 × 3 × 3 × 5. Divide out each factor as many times as it goes, and stop at √n, because whatever is left after that is itself prime.

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)            # what's left is a prime
    return factors

for n in [12, 97, 360, 1_000_000_007 * 3, 2 ** 20]:
    print(n, "=", " x ".join(map(str, prime_factors(n))))

Output:

12 = 2 x 2 x 3
97 = 97
360 = 2 x 2 x 2 x 3 x 3 x 5
3000000021 = 3 x 1000000007
1048576 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2

while d * d <= n is the same √n idea without a square root at all. Time O(√n), space O(number of factors).

Your turn: perfect number (solution)

Question. A perfect number equals the sum of its divisors, not counting itself: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14. Check it in O(√n).

Solution

When i divides n, add both i and its partner n // i. For a perfect square, i == n // i once (6 × 6 for 36), so add it only once. 1 is always a divisor; n itself is not counted, so the loop starts at 2.

import math

def is_perfect(n):
    if n < 2:
        return False
    total = 1                        # 1 divides every n > 1
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            total += i
            partner = n // i
            if partner != i:         # 6 x 6: count it once
                total += partner
    return total == n

print([n for n in range(1, 10_000) if is_perfect(n)])
print(is_perfect(33_550_336), is_perfect(36))

Output:

[6, 28, 496, 8128]
True False

Time O(√n), space O(1).

Practice questions (with solutions)

1. Count the primes between a and b (inclusive). 10 to 50 → 11.

Solution
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(n) + 1):
        if is_prime[i]:
            for multiple in range(i * i, n + 1, i):
                is_prime[multiple] = False
    return is_prime

flags = sieve(50)
print(sum(flags[10:51]), [k for k in range(10, 51) if flags[k]])

Output:

11 [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

sum of booleans counts the Trues (True is 1). flags[10:51] covers 10 to 50.

2. Twin primes below 100 (primes that differ by 2, like 11 and 13).

Solution
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(n) + 1):
        if is_prime[i]:
            for multiple in range(i * i, n + 1, i):
                is_prime[multiple] = False
    return is_prime

flags = sieve(102)
print([(p, p + 2) for p in range(2, 100) if flags[p] and flags[p + 2]])

Output:

[(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)]

3. Sum of all primes below 2 million.

Solution
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(n) + 1):
        if is_prime[i]:
            for multiple in range(i * i, n + 1, i):
                is_prime[multiple] = False
    return is_prime

flags = sieve(2_000_000)
print(sum(k for k in range(2, 2_000_000) if flags[k]))

Output:

142913828922

With is_prime per number this takes many seconds; with the sieve, well under a second. Python ints don't overflow, so the 12-digit sum is exact.

4. Is n a prime with all digits prime? (2, 3, 5, 7 only) e.g. 23, 37, 53.

Solution
import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

def all_prime_digits(n):
    return all(ch in "2357" for ch in str(n))

print([n for n in range(100) if is_prime(n) and all_prime_digits(n)])

Output:

[2, 3, 5, 7, 23, 37, 53, 73]

Quick quiz

How many numbers does this loop print?

import math
n = 121
for i in range(2, math.isqrt(n) + 1):
    print(i, end=" ")

(A) 9 numbers: 2 to 10 (B) 10 numbers: 2 to 11 (C) 119 numbers (D) 11 numbers: 1 to 11

Answer

(B). math.isqrt(121) is 11, so the range is range(2, 12): 2, 3, ..., 11. That's 10 numbers, and 11 is exactly the divisor that matters (11 × 11 = 121). Real output:

2 3 4 5 6 7 8 9 10 11 

Interview questions

  1. Why is checking divisors up to √n enough? Divisors come in pairs a × b = n; the smaller one of each pair is ≤ √n, so if none is found up to √n, there is none.
  2. Is 1 a prime number? No. A prime has exactly two different divisors, 1 and itself; 1 has only one.
  3. Why math.isqrt(n) + 1 and not int(n ** 0.5)? range stops before its end, so + 1 includes √n itself; isqrt is exact for any size of integer, while ** 0.5 goes through a float.
  4. What is the time complexity of the Sieve of Eratosthenes? O(n log log n) time, O(n) space.
  5. Why does the sieve start crossing out at i × i? Smaller multiples of i have a smaller prime factor and were crossed out already.
  6. When would you not use a sieve? For one huge number (say 10¹⁸): a list of 10¹⁸ booleans won't fit in memory. Use the √n check, or a probabilistic test like Miller–Rabin.
  7. Can you speed up the √n check further? Handle 2 separately, then try only odd divisors: range(3, math.isqrt(n) + 1, 2), about half the work (still O(√n)).
  8. What is an Armstrong number? A k-digit number equal to the sum of its digits each raised to the power k: 153, 370, 371, 407, 9474.
  9. How do you time code in Python? time.perf_counter() before and after; for small snippets, the timeit module repeats them many times.
  10. What does sum of a list of booleans give? The number of True values, because True == 1 and False == 0.

Glossary

Term Meaning Example
Divisor A number that divides n exactly (remainder 0) 3 is a divisor of 12
Prime number A whole number > 1 whose only divisors are 1 and itself 2, 3, 5, 7, 11
Composite number A whole number > 1 that is not prime 4, 9, 12
Perfect square A number that is a whole number squared 9, 25, 49
Square root (√n) The number that, squared, gives n √36 = 6
math.isqrt(n) Exact integer square root: the largest k with k² ≤ n math.isqrt(30) → 5
n ** 0.5 Square root through a float (can be off by one for huge n) 25 ** 0.5 → 5.0
Off-by-one error A loop that runs one time too few or too many range(2, 5) misses 5
range(a, b) Whole numbers from a up to but not including b range(2, 5) → 2, 3, 4
range(a, b, step) Every step-th number from a, stopping before b range(9, 31, 3) → 9, 12, ..., 30
Sieve of Eratosthenes Finds all primes up to n by crossing out multiples primes up to 30
Multiple n × some whole number multiples of 3: 3, 6, 9
Boolean list A list of True/False values, indexed by number is_prime[7] is True
time.perf_counter() A high-resolution stopwatch, in seconds end - start
Digit separator _ Underscores in number literals, for reading 1_000_000
Armstrong number k-digit number = sum of its digits to the power k 153, 9474
Augmented assignment Short form that updates a variable m //= 10
Prime factorisation Writing n as a product of primes 360 = 2³ × 3² × 5
Perfect number Equals the sum of its divisors except itself 6, 28, 496
Twin primes Two primes that differ by 2 (11, 13)
Time complexity How the number of steps grows with the input size O(√n)
Space complexity How the extra memory grows with the input size O(n) for the sieve
O(n) Grows in step with n try every divisor
O(√n) Grows with the square root of n 10⁸ → 10⁴ checks
O(n log log n) The sieve's time: almost linear in practice n = 10⁶ in a fraction of a second

Summary

  • 0 and 1 are not prime: check n < 2 first; an empty loop proves nothing.
  • Divisors come in pairs, so a prime check only needs divisors up to √n: O(√n) instead of O(n).
  • range stops before its end: use range(2, math.isqrt(n) + 1), or perfect squares look prime.
  • math.isqrt is exact; n ** 0.5 can be one off for huge numbers.
  • Many primes: the Sieve of Eratosthenes, crossing out multiples from i * i: O(n log log n) time, O(n) space.
  • Armstrong numbers: the power is the number of digits, not always 3.
  • Time code with time.perf_counter(), and compare the slow and fast versions.

Next episode: Number questions III: GCD and LCM (Euclid, math.gcd), factorial and big integers, the n-th Fibonacci number three ways.