2. Divisibility

VCMNA282: 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. Divibility 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(num), then string indexing, str(num)[-1], gets the last character.
 1import random
 2
 3
 4def is_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
13for _ in range(10):
14    num = random.randint(10, 300)
15    print(num, num/2, is_div_by_2(num))
Pseudocode:
function is_div_by_2(num)
endings ← [“0”, “2”, “4”, “6”, “8”]
last_digit ← str(num)[-1]
if last_digit in endings then
return true
else
return false
endif
endfunction

num ← random integer from 10 to 300
print num, is_div_by_2(num)

2.1.2. Divibility 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, is_div_by_3 checks if that sum is 3, 6, or 9.
 1import random
 2
 3
 4def is_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
26for _ in range(10):
27    num = random.randint(12, 300)
28    print(num, num/3, is_div_by_3(num))

2.1.3. Divibility 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.
 1import random
 2
 3
 4def is_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
13for _ in range(10):
14    num = random.randint(10, 300)
15    print(num, num/5, is_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.
 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 is_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
32for _ in range(10):
33    num = random.randint(12, 300)
34    print(num, num/7, is_div_by_7(num))

2.2. Other divisibility tests

2.2.1. Divibility by 6

A number is divisible by 2 and by 3.
 1import random
 2
 3
 4def is_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
13def is_div_by_3(num):
14    sum_of_digits = repeated_sum_digits(num)
15    if sum_of_digits in [3, 6, 9]:
16        return True
17    else:
18        return False
19
20
21def sum_digits(num):
22    sum = 0
23    for digit in str(num):
24        sum += int(digit)
25    return sum
26
27
28def repeated_sum_digits(num):
29    sum_of_digits = sum_digits(num)
30    while sum_of_digits > 10:
31        sum_of_digits = sum_digits(sum_of_digits)
32    return sum_of_digits
33
34
35def is_div_by_6(num):
36    if is_div_by_2(num) and is_div_by_2(num):
37        return True
38    else:
39        return False
40
41
42for _ in range(10):
43    num = random.randint(12, 300)
44    print(num, num/6, is_div_by_6(num))

2.2.2. Divibility by 10

A number is divisible by 10 if the last digit is 0.
For example: 120 is divisible by 10 since its last digit is 0.
The code below checks if the last digit is a 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.
 1import random
 2
 3
 4def is_div_by_10(num):
 5    endings = ["0"]
 6    last_digit = str(num)[-1]
 7    if last_digit in endings:
 8        return True
 9    else:
10        return False
11
12
13for _ in range(10):
14    num = random.randint(10, 300)
15    print(num, num/10, is_div_by_10(num))

2.2.3. Divibility by 4

A number is divisible by 4 if the last 2 digits are divisible by 4.
The code below checks if the last digit to see if it is divisible by 2, then divides it by 2 and checks again for divisibility by 2.
To get the last 2 digits, the number is converted to a string, str(num), then string indexing, str(num)[-2:], gets the last 2 characters.
 1import random
 2
 3
 4def is_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
13def is_divisible_by_4(num):
14    last_two_digits = int(str(num)[-2:])
15    if is_div_by_2(last_two_digits):
16        half_last_two_digits = int(last_two_digits / 2)
17        if is_div_by_2(half_last_two_digits):
18            return True
19        else:
20            return False
21    else:
22        return False
23
24
25for _ in range(10):
26    num = random.randrange(10, 300, 2)
27    print(num, num/4, is_divisible_by_4(num))
Pseudocode:
function is_div_by_2(num)
endings ← [“0”, “2”, “4”, “6”, “8”]
last_digit ← str(num)[-1]
if last_digit in endings then
return true
else
return false
endif
endfunction

function is_divisible_by_4(num)
last_two_digits ← int(str(num)[-2:])
if is_div_by_2(last_two_digits) then
half_last_two_digits ← int(last_two_digits / 2)
if is_div_by_2(half_last_two_digits) then
return true
else
return false
endif
else
return false
endif
endfunction

num ← random integer from 10 to 300
print num, is_divisible_by_4(num)

2.2.4. Divibility by 8

A number is divisible by 8 if the last 3 digits are divisible by 8.
The code below checks if the last digit to see if the last 3 digits are divisible by 2, then divides it by 2 and checks again for divisibility by 2, then divides it by 2 and checks again for divisibility by 2.
To get the last 3 digits, the number is converted to a string, str(num), then string indexing, str(num)[-3:], gets the last 3 characters.
 1import random
 2
 3
 4def is_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
13def is_divisible_by_8(num):
14    last_three_digits = int(str(num)[-3:])
15    if is_div_by_2(last_three_digits):
16        half_last_three_digits = int(last_three_digits / 2)
17        if is_div_by_2(half_last_three_digits):
18            quarter_last_three_digits = int(half_last_three_digits / 2)
19            if is_div_by_2(quarter_last_three_digits):
20                return True
21            else:
22                return False
23        else:
24            return False
25    else:
26        return False
27
28
29for _ in range(10):
30    num = random.randrange(10, 300, 2)
31    print(num, num/8, is_divisible_by_8(num))
32
33

2.2.5. Divibility by 9

A number is divisible by 9 if the sum of all digits is divisible by 9.
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, is_div_by_9 checks if that sum is 9.
 1import random
 2
 3
 4def is_div_by_9(num):
 5    sum_of_digits = repeated_sum_digits(num)
 6    if sum_of_digits in [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
26for _ in range(10):
27    num = random.randrange(12, 300, 3)
28    print(num, num/9, is_div_by_9(num))
29

2.2.6. General Divisibility by repeated addition

A general divisibility test can be done by counting up in steps equal to the divisor until the number to test is reached.
 1"""general divisor test by adding """
 2
 3def is_div_by_divisor(num,divisor):
 4    total = 0
 5    while total < num:
 6        total = total + divisor
 7    if total == num:
 8        return True
 9    else:
10        return False
11
12
13num = int(input("Type the number to test: "))
14divisor = int(input("Type the number you want to see if it is divisible by: "))
15print(num, "can be divided by", divisor, is_div_by_divisor(num,divisor))

2.2.7. Division by repeated subtraction

The code below returns the quotient and remainder from dividing a dividend by a divisor
eg. 7/3 = 2 remainder 1.
dividend is 7; divisor is 3; quotient is 2; remainder is 1
 1"""return text quotient and remainder from dividing dividend by divisor
 2    eg. 7/3 = 2 remainder 1.
 3    dividend is 7; divisor is 3; quotient is 2; remainder is 1
 4"""
 5
 6def quotient_and_remainder(dividend, divisor):
 7    quotient = 0
 8    remainder = dividend
 9    while remainder >= divisor:
10        remainder -= divisor
11        quotient +=1
12    return f'{dividend}/{divisor} = {quotient} R{remainder}'
13
14print(quotient_and_remainder(7, 3))
15