Computing the Divisors of a Number - Formula & Examples - Class 9 - Greatest Common Divisor as an Algorithm

part 2 - Computing the Divisors of a Number - Greatest Common Divisor as an Algorithm - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Computing the Divisors of a Number - Greatest Common Divisor as an Algorithm - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Computing the Divisors of a Number - Greatest Common Divisor as an Algorithm - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Computing the Divisors of a Number - Greatest Common Divisor as an Algorithm - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo Β· Class 9 Explore Class 9

Transcript

Computing the Divisors of a Number Suppose we want to find all divisors of 18 . Any positive divisor must lie between 1 and 18. A number greater than 18 cannot divide 18 into a positive whole-number quotient. The simplest approach is therefore: Check every integer from 1 to 18, keeping the ones that divide 18 exactly. We need somewhere to keep the results. The chapter uses a list. A list is written using square brackets: [1, 2, 3] An empty list is: [] Algorithm to find the divisors of 𝒏 Start with an empty list-of-divisors. For each number 𝑗 in the sequence 1,2,3,…,𝑛 : If 𝑗 divides 𝑛, add 𝑗 to the end of list-of-divisors. Report the completed list. Here: 𝑛 is the number whose divisors we want. 𝑗 is the candidate currently being checked. list-of-divisors stores the divisors found so far. The name 𝑗 does not have a special mathematical meaning here. It is simply a convenient name for the changing candidate. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Algorithm to find the divisors of 𝒏 Here: 𝒏 is the number whose divisors we want. 𝒋 is the candidate currently being checked. list-of-divisors stores the divisors found so far. The name 𝒋 does not have a special mathematical meaning here. It is simply a convenient name for the changing candidate. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Algorithm to find the divisors of 𝒏 Start with an empty list-of-divisors For each number 𝑗 in the sequence 1, 2, 3,…,𝑛 If 𝑗 divides 𝑛, add 𝑗 to the end of list-of-divisors Report the completed list. Executing the algorithm for 18 Following an algorithm step by step is called executing it. Candidate j | Does it divide 18? | List after checking 1 | Yes: (18)/(1)=18 | [1] 2 | Yes: (18)/(2)=9 | [1, 2] 3 | Yes: (18)/(3)=6 | [1, 2, 3] 4 | No | [1, 2, 3] 5 | No | [1, 2, 3] 6 | Yes: (18)/(6)=3 | [1, 2, 3, 6] 7,8 | No | [1, 2, 3, 6] 9 | Yes: (18)/(9)=2 | [1, 2, 3, 6, 9] 10 to 17 | No | Unchanged 18 | Yes: (18)/(18)=1 | [1, 2, 3, 6, 9, 18] Candidate j | Does it divide 18? | List after checking 1 | | [1] 2 | | [1, 2] 3 | | [1, 2, 3] 4 | No | [1, 2, 3] 5 | No | [1, 2, 3] 6 | | [1, 2, 3, 6] 7,8 | No | [1, 2, 3, 6] 9 | | [1, 2, 3, 6, 9] 10 to 17 | No | Unchanged 18 | | [1, 2, 3, 6, 9, 18] Thus: divisors(18)=[𝟏, 𝟐, πŸ‘, πŸ”, πŸ—, πŸπŸ–] Note: Numbers which fail the divisibility test are still checked, but are not stored Why is the list in increasing order? We examine candidates in this order: 1, 2, 3,…,18 Each new divisor is therefore greater than the divisors already recorded. Appending it to the end preserves increasing order. Why does this algorithm work? Every possible positive divisor lies between 1 and 𝑛, so none is missed. A number is added only if it divides 𝑛, so no incorrect entry is included. There are only 𝑛 candidates, so the process stops. What basic operation does it assume? It assumes we already know how to check whether one number divides another exactly. For example To test 5 as a divisor of 18: (18)/(5)=3(3)/(5) Since the remainder is not zero, we reject 5 A number is added only if it divides 𝑛, so no incorrect entry is included. There are only 𝑛 candidates, so the process stops. What basic operation does it assume? It assumes we already know how to check whether one number divides another exactly. For example To test 5 as a divisor of 18: (18)/(5)=3(3)/(5) Since the remainder is not zero, we reject 5 Let’s look at more examples

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.