Taking digits of a number
A computer cannot look at a number like you do. It peels digits off one at a time with two small tools.
- n % 10 is the remainder when n is divided by 10. It is the last digit. 472 % 10 = 2.
- n ÷ 10 (whole-number division) throws that digit away. 472 ÷ 10 = 47.
Repeat while n is not 0. Add each digit you take to a running total to get the sum of digits: 2 + 7 + 4 = 13. Count the loops to get the number of digits. Build rev = rev × 10 + digit to get the reverse of the number.
Why it stops
Each loop makes n about ten times smaller. After as many loops as there are digits, n becomes 0 and the loop ends.
Divisors, multiples and primes
A divisor of n divides n with remainder 0. A multiple of n is n × 1, n × 2, n × 3 and so on.
Divisors come in pairs: if 2 divides 12 then so does 12 ÷ 2 = 6. So a program only needs to test numbers up to the square root of n. For 36 the pairs are (1, 36), (2, 18), (3, 12), (4, 9) and the single 6.
A prime has exactly two divisors: 1 and itself (2, 3, 5, 7, 11…). The number 1 is not prime. A number with more divisors is composite.
Prime factorisation
Every number bigger than 1 can be written as a product of primes in exactly one way (apart from order). To find it, divide by the smallest prime that works, again and again.
Example: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5, ÷ 5 = 1. So 360 = 2³ × 3² × 5.
Use it to count divisors: add 1 to each power and multiply. For 360 that is (3 + 1)(2 + 1)(1 + 1) = 24 divisors.
Euclid's algorithm for HCF
The HCF (highest common factor, also called GCD) is the biggest number that divides both a and b.
By subtraction
Replace the bigger number by the difference of the two. Repeat until the numbers are equal. HCF(48, 18): 48 − 18 = 30, 30 − 18 = 12, 18 − 12 = 6, 12 − 6 = 6. The equal pair is (6, 6), so the HCF is 6. In the 3D this is cutting squares.
By division (faster)
Write a = q × b + r. Then HCF(a, b) = HCF(b, r). Stop when r = 0; the last divisor is the HCF. 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so the HCF is 6.
Bonus: LCM = a × b ÷ HCF.
Changing number base
Our usual numbers are base 10: ten digits 0 to 9. Computers use base 2 (binary): only 0 and 1. In base b, the digits of a number are place values that are powers of b.
Decimal to base b
Divide by b again and again. Write the remainders. Read them from last to first. 13 → 13 ÷ 2 = 6 r 1, 6 ÷ 2 = 3 r 0, 3 ÷ 2 = 1 r 1, 1 ÷ 2 = 0 r 1. Read upward: 1101.
Base b to decimal
Multiply each digit by its place value and add. 1101₂ = 8 + 4 + 0 + 1 = 13.
Try it: an algorithm with matchsticks
Take 48 matchsticks and 18 pins. Make the biggest equal groups with nothing left over. Count how many groups you can make. Check it with Euclid's method. Then write 13 as lamps (8, 4, 1) with a friend: who can write their age in binary first?
Key formulas and definitions
- Last digit = n % 10; the rest = n ÷ 10
- a = q × b + r, with 0 ≤ r < b
- HCF(a, b) = HCF(b, a mod b); stop when the remainder is 0
- HCF × LCM = a × b
- Number of divisors from n = p^x · q^y · r^z is (x+1)(y+1)(z+1)
- Value in base b: d₂·b² + d₁·b + d₀
Worked examples
1. Find the sum of the digits of 2468 using the n % 10 method.
2468 % 10 = 8, n = 246. 246 % 10 = 6, n = 24. 24 % 10 = 4, n = 2. 2 % 10 = 2, n = 0. Sum = 8 + 6 + 4 + 2 = 20.
2. Reverse the number 1234 with rev = rev × 10 + digit.
rev = 0. Digit 4: rev = 4. Digit 3: rev = 43. Digit 2: rev = 432. Digit 1: rev = 4321. The reverse is 4321.
3. List all divisors of 36.
Test 1 to 6 (the square root): 1, 2, 3, 4, 6 divide 36. Their partners are 36, 18, 12, 9, 6. So the divisors are 1, 2, 3, 4, 6, 9, 12, 18, 36 (nine of them).
4. Write 360 as a product of primes and count its divisors.
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Divisors = (3 + 1)(2 + 1)(1 + 1) = 24.
5. Find HCF(84, 36) by the division method, then the LCM.
84 = 2 × 36 + 12. 36 = 3 × 12 + 0. The last divisor is 12, so HCF = 12. LCM = 84 × 36 ÷ 12 = 252.
6. Convert 45 to binary.
45 ÷ 2 = 22 r 1; 22 ÷ 2 = 11 r 0; 11 ÷ 2 = 5 r 1; 5 ÷ 2 = 2 r 1; 2 ÷ 2 = 1 r 0; 1 ÷ 2 = 0 r 1. Read upward: 101101. Check: 32 + 8 + 4 + 1 = 45.
7. Convert 11010 (binary) to decimal.
Place values from the right: 1, 2, 4, 8, 16. 1·16 + 1·8 + 0·4 + 1·2 + 0·1 = 16 + 8 + 2 = 26.
8. Convert 45 to base 5.
45 ÷ 5 = 9 r 0; 9 ÷ 5 = 1 r 4; 1 ÷ 5 = 0 r 1. Read upward: 140 in base 5. Check: 25 + 4 × 5 + 0 = 45.
Common mistakes
- Reading the remainders from first to last when changing base. Always read them from last to first.
- Calling 1 a prime number. A prime needs exactly two divisors, and 1 has only one.
- Stopping Euclid's method one step early. Stop only when the remainder is 0; the HCF is the divisor of that last step.
- Mixing up divisor and multiple. 3 is a divisor of 12; 24 is a multiple of 12.