The World of Algorithms

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

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