Algorithms with factors & multiples
Theory
An algorithm is a set of steps that always gives the right answer if you follow it exactly. This Year 5 maths page shows algorithms and flow charts that test whether one number is a factor or multiple of another, algorithms that repeat steps to list factors and multiples, a sieve for finding prime numbers, and how to find the highest common factor and lowest common multiple.
An algorithm is a list of steps carried out in order. Some steps make a decision (a yes or no question) that decides which step comes next. Some steps are repeated until a condition is met.
A flow chart draws an algorithm with boxes and arrows. A diamond holds a yes or no question, with one arrow for each answer.
\(a\) is a factor of \(b\) when \(b \div a\) has no remainder. Then \(b\) is a multiple of \(a\).
A prime number can only be made as \(1 \times\) itself, so it has exactly two factors, like \(13\). A number with more than two factors, like \(15\), is called composite. The number \(1\) is neither.
The highest common factor (HCF) of two numbers is the largest number that divides both. The lowest common multiple (LCM) is the smallest number that both divide.
The tests behind these algorithms:
Algorithm: is \(a\) a factor of \(b\)?
- Divide \(b\) by \(a\).
- Is the remainder \(0\)? If yes, \(a\) is a factor of \(b\) and \(b\) is a multiple of \(a\).
- If no, \(a\) is not a factor and \(b\) is not a multiple of \(a\).
Algorithm: list the multiples of \(a\) up to a limit
- Start with \(a\).
- Add \(a\) to get the next multiple.
- Repeat step 2 until the next number would pass the limit.
Algorithm: highest common factor and lowest common multiple
- HCF: list the factors of both numbers and take the largest number in both lists.
- LCM: list multiples of the larger number until you reach one that the smaller number divides exactly.
| \(60 \div 9\) | \(=\) | \(6 \text{ r } 6\) |
| \(\text{remainder} = 0?\) | \(:\) | \(\text{No}\) |
Follow the No arrow: \(9\) is not a factor of \(60\).
| \(63 \div 7\) | \(=\) | \(9 \text{ r } 0\) |
| \(\text{remainder} = 0?\) | \(:\) | \(\text{Yes}\) |
Yes, \(63\) is a multiple of \(7\), because \(7 \times 9 = 63\).
(i) Which numbers are written?
(ii) How many multiples of \(7\) are between \(1\) and \(60\)?
| \(7,\ 14,\ 21,\ 28\) | \(,\) | \(35,\ 42,\ 49,\ 56\) |
| \(56 + 7\) | \(=\) | \(63 > 60 \text{ (stop)}\) |
(i) \(7,\ 14,\ 21,\ 28,\ 35,\ 42,\ 49,\ 56\).
(ii) \(8\).
| \(39 \div 3\) | \(=\) | \(13\) |
\(39 = 3 \times 13\), so it has more than two factors (\(1,\ 3,\ 13,\ 39\)). It is composite.
| \(28\) | \(:\) | \(1,\ 2,\ 4,\ 7,\ 14,\ 28\) |
| \(42\) | \(:\) | \(1,\ 2,\ 3,\ 6,\ 7,\ 14,\) |
| \(\) | \(\) | \(21,\ 42\) |
The common factors are \(1,\ 2,\ 7,\ 14\). The HCF is \(14\).
| \(\text{multiples of } 15\) | \(:\) | \(15,\ 30\) |
| \(30 \div 6\) | \(=\) | \(5\) |
The LCM of \(6\) and \(15\) is \(30\), so they flash together again after \(30\) seconds.
| \(\text{HCF of } 20 \text{ and } 30\) | \(=\) | \(10\) |
| \(20 \div 10,\ 30 \div 10\) | \(:\) | \(2,\ 3\) |
\(10\) packs, each with \(2\) pens and \(3\) pencils.
(i) find the HCF
(ii) find the LCM
(iii) multiply your answers.
| \(\text{HCF}\) | \(=\) | \(5\) |
| \(\text{LCM}\) | \(=\) | \(30\) |
| \(5 \times 30\) | \(=\) | \(150\) |
(i) \(5\).
(ii) \(30\).
(iii) \(150\), the same as \(10 \times 15\).
Common pitfalls
Frequently asked questions
What is an algorithm?
An algorithm is a set of steps that you follow in order to solve a problem. It can include decisions and steps that repeat.
How do you test whether one number is a factor of another?
Divide. If the remainder is \(0\), it is a factor. \(56 \div 8 = 7\) with no remainder, so \(8\) is a factor of \(56\).
What does the diamond in a flow chart mean?
A diamond holds a yes or no question. You follow the arrow that matches your answer.
What is a prime number?
A prime number has exactly two factors, \(1\) and itself. \(2,\ 3,\ 5,\ 7\) and \(11\) are prime.
What is the highest common factor?
It is the largest number that divides both numbers exactly. The HCF of \(28\) and \(42\) is \(14\).
What is the lowest common multiple?
It is the smallest number that is a multiple of both numbers. The LCM of \(6\) and \(15\) is \(30\).