Worksheets › Class 9 › The World of Algorithms › Cheat sheet
Class 9 The World of Algorithms: cheat sheet
CBSE Mathematics. An algorithm is a finite list of clear steps. Euclid’s algorithm finds the HCF by repeated division; others add, convert to binary or find primes.
Key ideas
- Every algorithm must be clear at each step and must stop after a finite number of steps.
- Euclid’s algorithm: divide the larger number by the smaller, then divide the divisor by the remainder, until the remainder is 0. The last divisor is the HCF.
- Repeated subtraction (Euclid’s older method) gives the same HCF but takes longer.
- Column addition works right to left; a column that adds to 10 or more carries 1 to the next column.
- Binary: divide by 2 again and again and read the remainders from the bottom up.
- The sieve of Eratosthenes finds primes by crossing out the multiples of each prime in turn.
Remember
| Division step | a = bq + r, with 0 ≤ r < b |
| Euclid | HCF(a, b) = HCF(b, r) |
| HCF and LCM | HCF(a, b) × LCM(a, b) = a × b |
| Three numbers | HCF(a, b, c) = HCF(HCF(a, b), c) |
Watch out
- Taking the last remainder (0) as the HCF instead of the last divisor.
- Reading binary remainders from the top instead of the bottom.
- Forgetting a carry when a column adds to exactly 10.
Worked example
Write 118 in binary by repeated division by 2.
Working: 118 ÷ 2 = 59 r 0; 59 ÷ 2 = 29 r 1; 29 ÷ 2 = 14 r 1; 14 ÷ 2 = 7 r 0; 7 ÷ 2 = 3 r 1; 3 ÷ 2 = 1 r 1; 1 ÷ 2 = 0 r 1; read the remainders upwards
Answer: 1110110
Practise The World of Algorithms
Revise with this page, then practise: every The World of Algorithms sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.