2. Divisibility

VC2M8A04 level 8 Use algorithms and related testing procedures to identify and correct errors.

  • testing a number for divisibility

2.1. Prime number divisibility tests

2.1.1. Divisibility by 2

A number is divisible by 2 if the last digit is 0, 2, 4, 6 or 8.
For example: 234 is divisible by 2, because the last digit is 4.
The code below checks if the last digit to see if it is divisible by 2.
To get the last digit, the number is converted to a string, str(number), then string indexing, str(number)[-1], gets the last character.
The pseudocode for the algorithm is as follows:
FUNCTION DIV_BY_2(num)
    endings ← ["0", "2", "4", "6", "8"]
    last_digit ← LAST CHARACTER OF STRING(num)

    IF last_digit IN endings THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION


BEGIN
    num ← RANDOM INTEGER BETWEEN 10 AND 300
    result ← DIV_BY_2(num)
    PRINT num, result
END
The python code implementing the algorithm is shown below:
 1import random
 2
 3
 4def div_by_2(num):
 5    endings = ["0", "2", "4", "6", "8"]
 6    last_digit = str(num)[-1]
 7    if last_digit in endings:
 8        return True
 9    else:
10        return False
11
12
13num = random.randint(10, 300)
14print(num, div_by_2(num))
15

2.1.2. Divisibility by 3

A number is divisible by 3 if the sum of the digits in the number is divisible by 3.
For example: 162 is divisible by 3 since the sum of the digits is 9 (1 + 6 + 2 = 9) and 9 is divisible

by 3. | The code below sums the digits of the number via sum_digits, and repeats summing the digits via repeated_sum_digits until there is just one digit, then, in div_by_3, checks if that sum is 3, 6, or 9.

The pseudocode for the algorithm is as follows:
FUNCTION DIV_BY_3(num)
    sum_of_digits ← REPEATED_SUM_DIGITS(num)

    IF sum_of_digits IN [3, 6, 9] THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION


FUNCTION SUM_DIGITS(num)
    total ← 0
    FOR each digit IN STRING(num)
        total ← total + INTEGER(digit)
    ENDFOR
    RETURN total
ENDFUNCTION


FUNCTION REPEATED_SUM_DIGITS(num)
    sum_of_digits ← SUM_DIGITS(num)

    WHILE sum_of_digits > 10
        sum_of_digits ← SUM_DIGITS(sum_of_digits)
    ENDWHILE

    RETURN sum_of_digits
ENDFUNCTION


BEGIN
    num ← RANDOM INTEGER BETWEEN 12 AND 300
    result ← DIV_BY_3(num)
    PRINT num, result)
END
The python code implementing the algorithm is shown below:
 1import random
 2
 3
 4def div_by_3(num):
 5    sum_of_digits = repeated_sum_digits(num)
 6    if sum_of_digits in [3, 6, 9]:
 7        return True
 8    else:
 9        return False
10
11
12def sum_digits(num):
13    sum = 0
14    for digit in str(num):
15        sum += int(digit)
16    return sum
17
18
19def repeated_sum_digits(num):
20    sum_of_digits = sum_digits(num)
21    while sum_of_digits > 10:
22        sum_of_digits = sum_digits(sum_of_digits)
23    return sum_of_digits
24
25
26num = random.randint(12, 300)
27print(num, div_by_3(num))

2.1.3. Divisibility by 5

A number is divisible by 5 if the last digit is either 0 or 5.
For example: 125 and 120 are both divisible by 5 since their last digits are 5 and 0.
The code below checks if the last digit is a 5 or 0.
To get the last digit, the number is converted to a string, str(num), then string indexing, str(num)[-1], gets the last character.
The pseudocode for the algorithm is as follows:
FUNCTION DIV_BY_5(num)
    endings ← ["0", "5"]
    last_digit ← LAST CHARACTER OF STRING(num)

    IF last_digit IN endings THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION


BEGIN
    num ← RANDOM INTEGER BETWEEN 10 AND 300
    result ← DIV_BY_5(num)
    PRINT num, result)
END
The python code implementing the algorithm is shown below:
 1import random
 2
 3
 4def div_by_5(num):
 5    endings = ["0", "5"]
 6    last_digit = str(num)[-1]
 7    if last_digit in endings:
 8        return True
 9    else:
10        return False
11
12
13num = random.randint(10, 300)
14print(num, div_by_5(num))

2.1.4. Divisibility by 7

The process for divisibility by 7 requires a few steps. Follow the steps below to test divisibility by 7, and then work through the example provided.
1. Write down all the digits in the number except the last digit.
2. Take the last digit of the number you’re testing and double it.
3. Subtract this number from the rest of the digits in the original number that you wrote down.
4. If this new number is either 0 or a number that’s divisible by 7, then the original number is also divisible by 7.
5. If you can’t tell yet if the new number is divisible by 7, go back to the first step with this new (smaller) number and repeat.
The pseudocode for the algorithm is as follows:
FUNCTION DIV_BY_7(num)
    diff ← REPEATED_DIFF_FROM_DBL_LAST(num)

    IF diff IN [0, 7, -7] THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION


FUNCTION DIFF_FROM_DBL_LAST(num)
    last ← INTEGER(LAST CHARACTER OF STRING(num))
    all_but_last ← INTEGER(STRING(num) WITHOUT LAST CHARACTER)
    RETURN all_but_last - 2 * last
ENDFUNCTION


FUNCTION REPEATED_DIFF_FROM_DBL_LAST(num)
    diff ← DIFF_FROM_DBL_LAST(num)

    WHILE diff > 10
        diff ← DIFF_FROM_DBL_LAST(diff)
    ENDWHILE

    RETURN diff
ENDFUNCTION


BEGIN
    num ← RANDOM INTEGER BETWEEN 12 AND 300
    result ← DIV_BY_7(num)
    PRINT num, result)
END
The python code implementing the algorithm is shown below:
 1# The process for divisibility by 7 requires a few steps. Follow the steps below to test divisibility by 7, and then work through the example provided.
 2# 1.	Write down all the digits in the number except the last digit.
 3# 2.	Take the last digit of the number you're testing and double it. 
 4# 3.	Subtract this number from the rest of the digits in the original number that you wrote down. 
 5# 4.	If this new number is either 0 or a number that's divisible by 7, then the original number is also divisible by 7. 
 6# 5.	If you can't tell yet if the new number is divisible by 7, go back to the first step with this new (smaller) number and repeat. 
 7
 8import random
 9
10
11def div_by_7(num):
12    diff = repeated_diff_from_dbl_last(num)
13    if diff in [0, 7, -7]:
14        return True
15    else:
16        return False
17
18
19def diff_from_dbl_last(num):
20    last = int(str(num)[-1])
21    all_but_last = int(str(num)[:-1])
22    return all_but_last - 2 * last
23
24
25def repeated_diff_from_dbl_last(num):
26    diff = diff_from_dbl_last(num)
27    while diff > 10:
28        diff = diff_from_dbl_last(diff)
29    return diff
30
31
32num = random.randint(12, 300)
33print(num, div_by_7(num))