Last updated at October 28, 2026 by Teachoo
Transcript
Question 3 Write an algorithm prime(n) to check if n is prime. (Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?) A prime number is an integer greater than 1 having exactly two distinct positive divisors: 1 and the number itself We already have an algorithm divisors (π), so we can reuse it. How we arrive at the algorithm Find all positive divisors of π Count them If there are exactly two, π is prime Otherwise, it is not prime Algorithm to check whether π is prime If π<2, report "not prime" and stop Let list-of-divisors be the list obtained by computing divisors (π) Count the entries in list-of-divisors If there are exactly two entries, report "prime" Otherwise, report "not prime" Example 1: π=ππ divisors (13)=[1, 13] There are exactly two entries β΄ 13 is prime Example 2: π=ππ divisors (12)=[1, 2, 3, 4, 6, 12] There are six entries So, 12 is not prime Example 3: π=π Since 1<2, report "not prime" Letβs check divisors divisors(1) = [1] Since it has only one entry So, 1 is not prime Otherwise, it is not prime Algorithm to check whether π is prime If π<2, report "not prime" and stop Let list-of-divisors be the list obtained by computing divisors (π) Count the entries in list-of-divisors If there are exactly two entries, report "prime" Otherwise, report "not prime" Example 1: π=ππ divisors (13)=[1, 13] There are exactly two entries β΄ 13 is prime Example 2: π=ππ divisors (12)=[1, 2, 3, 4, 6, 12] There are six entries So, 12 is not prime Example 3: π=π Since 1<2, report "not prime" Letβs check divisors divisors(1) = [1] Since it has only one entry So, 1 is not prime Example 2: π=ππ divisors (12)=[1, 2, 3, 4, 6, 12] There are six entries So, 12 is not prime Example 3: π=π Since 1<2, report "not prime" Letβs check divisors divisors(1) = [1] Since it has only one entry So, 1 is not prime