Question 3 - Write an algorithm prime(n) to check if n is prime - End-of-Chapter Exercises

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

part 3 - Question 3 - 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 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

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.