• Practice
  • About 14 min
  • 5 practice questions

Classic algorithm problems: primes, factorial, Fibonacci, digits and palindromes

Solve and trace the standard algorithm questions: prime test, factorial, Fibonacci series, digit sum, reversing a number and palindrome check.

If something looks wrong, please tell us.

Certain small algorithms appear again and again in papers because each one uses a loop and a few operators. If you know the idea behind each, you can trace any variation. This lesson gives the idea, a short pseudocode outline and a worked trace for each. All numbers are illustrative.

The standard algorithms

Seven standard algorithms
TaskIdeaKey statements
Factorial of nMultiply 1 x 2 x ... x nf = 1; FOR i = 1 TO n: f = f * i
Sum of digitsPeel off the last digit with % 10, then drop it with / 10WHILE n > 0: s = s + n % 10; n = n / 10
Reverse a numberBuild the reverse digit by digitr = r * 10 + n % 10; n = n / 10
Palindrome numberReverse it and compare with the originalIF reverse == original
Prime testTry divisors from 2 up to the square rootIF n % d == 0 THEN not prime
Fibonacci seriesEach term is the sum of the previous twoc = a + b; a = b; b = c
GCD (Euclid)Replace (a, b) by (b, a % b) until b is 0WHILE b != 0: t = a % b; a = b; b = t

Worked example 1: prime test

Is 29 prime? Test divisors from 2 up to the square root of 29, which is about 5.4, so test 2, 3 and 5. 29 % 2 = 1, 29 % 3 = 2, 29 % 5 = 4. None divides it, so 29 is prime. Is 91 prime? 91 % 2 = 1, 91 % 3 = 1, 91 % 5 = 1, 91 % 7 = 0. A divisor was found, so 91 is not prime (91 = 7 x 13). Only one divisor needs to be found to reject a number.

Worked example 2: factorial

Factorial of 7: f starts at 1. As i goes from 1 to 7, f becomes 1, 2, 6, 24, 120, 720 and 5040. The result is 5040. Factorial of 0 is defined as 1, so the loop must start with f = 1, not 0.

Worked example 3: digit sum and reverse

Trace for n = 4829. Digit sum: 4829 % 10 = 9, s = 9, n = 482; 482 % 10 = 2, s = 11, n = 48; 48 % 10 = 8, s = 19, n = 4; 4 % 10 = 4, s = 23, n = 0. The sum is 23. Reverse of 1234: r = 0; digit 4 gives r = 4, n = 123; digit 3 gives r = 43, n = 12; digit 2 gives r = 432, n = 1; digit 1 gives r = 4321, n = 0. The reverse is 4321.

Worked example 4: palindrome and Fibonacci

Is 1331 a palindrome? Its reverse is 1331, which equals the original, so yes. Is 1234? Its reverse 4321 differs, so no. Fibonacci: starting with 0 and 1, the first ten terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. The sum of the first eight terms is 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33.

Worked example 5: Euclid's GCD

gcd(60, 24): 60 % 24 = 12, so the pair becomes (24, 12). 24 % 12 = 0, so the pair becomes (12, 0). When b is 0 the answer is a, which is 12.

Peel digits with % 10 and / 10; test divisors only up to the square root; Euclid replaces (a, b) by (b, a % b).

Common traps

  • Starting a factorial product at 0, which makes the answer 0.
  • Forgetting to update n inside a digit loop, so it never ends.
  • Treating 1 as prime; a prime has exactly two factors.
  • Testing all divisors up to n when only the square root is needed.

Check your understanding

  1. 1. Which operator gives the last digit of a whole number n?

    1. n / 10
    2. n * 10
    3. n % 10
    4. n - 10
    Show answer

    Answer: C. The remainder after dividing by 10 is the last digit.

  2. 2. What is the factorial of 5?

    1. 25
    2. 210
    3. 120
    4. 240
    Show answer

    Answer: C. 1 x 2 x 3 x 4 x 5 = 120.

  3. 3. Which of these numbers is prime?

    1. 53
    2. 57
    3. 49
    4. 51
    Show answer

    Answer: A. 51 = 3 x 17, 57 = 3 x 19 and 49 = 7 x 7; 53 has no divisor from 2 to 7, so it is prime.

  4. 4. The digit sum of 7305 is

    1. 12
    2. 15
    3. 10
    4. 20
    Show answer

    Answer: B. 7 + 3 + 0 + 5 = 15.

  5. 5. Which number is a palindrome?

    1. 1223
    2. 1231
    3. 1212
    4. 1221
    Show answer

    Answer: D. 1221 reads the same forwards and backwards.

Privacy · Terms · Refunds · Delivery