8. Classic Math Algorithms

Classic Math Algorithms

These four algorithms show up again and again in programming courses and interviews. Each uses a loop with a clear changing state, so trace tables are the best way to understand them.

Example (a): Check if a number is prime

Problem

A prime number (2, 3, 5, 7, 11, ...) has exactly two divisors: 1 and itself. Decide whether N is prime by testing every possible divisor from 2 up to N-1: if any divides N evenly, N is not prime.

Reading the chart: the inner diamond asks "does i divide N?". If Yes we set isPrime = false and leave the loop; if No we add 1 to i and check the next divisor. When i passes N-1 with isPrime still true, N is prime.

Pseudocode

INPUT N
SET isPrime = true
SET i = 2
WHILE i <= N - 1
    IF N % i == 0
        SET isPrime = false
    SET i = i + 1
IF isPrime == true
    OUTPUT "prime"
ELSE
    OUTPUT "not prime"

Trace table

Sample input: N = 7. We test i = 2, 3, 4, 5, 6. None divide 7 evenly, so the remainder (N % i) is never 0 and isPrime stays true.

Iteration	i	i <= 6 ?	7 % i	divides evenly?	isPrime
start	2	-	-	-	true
1	2	Yes	1	No	true
2	3	Yes	1	No	true
3	4	Yes	3	No	true
4	5	Yes	2	No	true
5	6	Yes	1	No	true
exit	7	No	-	-	true

isPrime is still true, so 7 is prime. (If we had tried N = 9, then at i = 3 the remainder 9 % 3 would be 0, isPrime would flip to false, and 9 would be "not prime".)

In Python

N = 7
is_prime = True
i = 2
while i <= N - 1:
    if N % i == 0:
        is_prime = False
    i = i + 1
if is_prime and N >= 2:
    print("prime")
else:
    print("not prime")

# Output:
# prime

Example (b): Greatest common divisor (Euclid's algorithm)

Problem

The greatest common divisor (GCD) of two numbers is the largest number that divides both. Euclid's algorithm finds it fast: keep replacing the pair (a, b) with (b, a % b) until b becomes 0; then a is the answer.

Pseudocode

INPUT a, b
WHILE b != 0
    SET temp = a % b
    SET a = b
    SET b = temp
OUTPUT a

Trace table

Sample input: a = 48, b = 36. Watch both a and b each step.

Iteration	a (before)	b (before)	b != 0 ?	temp = a % b	a after (= old b)	b after (= temp)
1	48	36	Yes	48 % 36 = 12	36	12
2	36	12	Yes	36 % 12 = 0	12	0
exit	12	0	No	-	12	0

When b reaches 0 the loop stops and a = 12 is the GCD of 48 and 36.

In Python

a = 48
b = 36
while b != 0:
    temp = a % b
    a = b
    b = temp
print(a)

# Output:
# 12

Example (c): First N Fibonacci numbers

Problem

The Fibonacci sequence starts 0, 1 and every later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... Print the first N of them.

Pseudocode

INPUT N
SET prev = 0
SET curr = 1
FOR i FROM 1 TO N
    OUTPUT prev
    SET next = prev + curr
    SET prev = curr
    SET curr = next

Trace table

Sample input: N = 7. The printed number each pass is the prev value.

Iteration (i)	prev (printed)	curr	next = prev + curr	prev after	curr after
start	0	1	-	0	1
1	0	1	0 + 1 = 1	1	1
2	1	1	1 + 1 = 2	1	2
3	1	2	1 + 2 = 3	2	3
4	2	3	2 + 3 = 5	3	5
5	3	5	3 + 5 = 8	5	8
6	5	8	5 + 8 = 13	8	13
7	8	13	8 + 13 = 21	13	21

Numbers printed: 0 1 1 2 3 5 8.

In Python

N = 7
prev = 0
curr = 1
for i in range(N):
    print(prev, end=" ")
    next_num = prev + curr
    prev = curr
    curr = next_num
print()

# Output:
# 0 1 1 2 3 5 8

Example (d): Compute x raised to the power n with a loop

Problem

Work out x to the power n (x multiplied by itself n times) without using a built-in power operator. For example 2 to the power 5 is 2 x 2 x 2 x 2 x 2 = 32.

Pseudocode

INPUT x, n
SET result = 1
SET i = 1
WHILE i <= n
    SET result = result * x
    SET i = i + 1
OUTPUT result

Trace table

Sample input: x = 2, n = 5. The accumulator result starts at 1 and gets multiplied by x each pass.

Iteration	i	i <= 5 ?	result = result * 2	result after	i after
start	1	-	-	1	1
1	1	Yes	1 * 2	2	2
2	2	Yes	2 * 2	4	3
3	3	Yes	4 * 2	8	4
4	4	Yes	8 * 2	16	5
5	5	Yes	16 * 2	32	6
exit	6	No	-	32	6

2 to the power 5 = 32.

In Python

x = 2
n = 5
result = 1
i = 1
while i <= n:
    result = result * x
    i = i + 1
print(result)

# Output:
# 32