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
nis a numberdthat dividesnexactly: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_000is 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
- 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. - Is 1 a prime number? No. A prime has exactly two different divisors, 1 and itself; 1 has only one.
- Why
math.isqrt(n) + 1and notint(n ** 0.5)?rangestops before its end, so+ 1includes √n itself;isqrtis exact for any size of integer, while** 0.5goes through a float. - What is the time complexity of the Sieve of Eratosthenes? O(n log log n) time, O(n) space.
- Why does the sieve start crossing out at i × i? Smaller multiples of i have a smaller prime factor and were crossed out already.
- 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.
- 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)). - 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.
- How do you time code in Python?
time.perf_counter()before and after; for small snippets, thetimeitmodule repeats them many times. - What does
sumof a list of booleans give? The number ofTruevalues, becauseTrue == 1andFalse == 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 < 2first; 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).
rangestops before its end: userange(2, math.isqrt(n) + 1), or perfect squares look prime.math.isqrtis exact;n ** 0.5can 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.