Question 4 - Write an algorithm primedivisors(n) to compute the list - End-of-Chapter Exercises

part 2 - Question 4 - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Question 4 - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo ยท Class 9 Explore Class 9

Transcript

Question 4 Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers. (Hint: Compute divisors(n) and then filter out the primes in this list.) We want a list containing the divisors of ๐‘› that are prime. For example, 12 has divisors: divisors (2) = [1, 2, 3, 4, 6, 12] Only 2 and 3 are prime, so: primedivisors(12) =[๐Ÿ, ๐Ÿ‘] How we arrive at the algorithm We already know how to: Find divisors using divisors (๐’) Test if prime using prime (๐’™) We just combine these procedures. Algorithm Compute list-of-divisors using divisors (๐‘›) Start with an empty list prime-divisors For each number ๐‘ฅ in list-of-divisors Apply prime(๐‘ฅ) If ๐‘ฅ is prime, add it to prime-divisors Report prime-divisors Example: ๐’=๐Ÿ‘๐ŸŽ First: divisors(30)=[1, 2, 3, 5, 6, 10, 15, 30] Now, we test each entry Therefore: primedivisors(30) = [2, 3, 5] Divisor | Prime? | prime-divisors 1 | No | [] 2 | Yes | [2] 3 | Yes | [2, 3] 5 | Yes | [2, 3, 5] 6 | No | [2, 3, 5] 10 | No | [2, 3, 5] 15 | No | [2, 3, 5] 30 | No | [2, 3, 5]

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.