Last updated at October 28, 2026 by Teachoo
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]