- 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
| Task | Idea | Key statements |
|---|---|---|
| Factorial of n | Multiply 1 x 2 x ... x n | f = 1; FOR i = 1 TO n: f = f * i |
| Sum of digits | Peel off the last digit with % 10, then drop it with / 10 | WHILE n > 0: s = s + n % 10; n = n / 10 |
| Reverse a number | Build the reverse digit by digit | r = r * 10 + n % 10; n = n / 10 |
| Palindrome number | Reverse it and compare with the original | IF reverse == original |
| Prime test | Try divisors from 2 up to the square root | IF n % d == 0 THEN not prime |
| Fibonacci series | Each term is the sum of the previous two | c = a + b; a = b; b = c |
| GCD (Euclid) | Replace (a, b) by (b, a % b) until b is 0 | WHILE 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. Which operator gives the last digit of a whole number n?
- n / 10
- n * 10
- n % 10
- n - 10
Show answer
Answer: C. The remainder after dividing by 10 is the last digit.
-
2. What is the factorial of 5?
- 25
- 210
- 120
- 240
Show answer
Answer: C. 1 x 2 x 3 x 4 x 5 = 120.
-
3. Which of these numbers is prime?
- 53
- 57
- 49
- 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. The digit sum of 7305 is
- 12
- 15
- 10
- 20
Show answer
Answer: B. 7 + 3 + 0 + 5 = 15.
-
5. Which number is a palindrome?
- 1223
- 1231
- 1212
- 1221
Show answer
Answer: D. 1221 reads the same forwards and backwards.
Sign in to keep track of the lessons you finish.