NEWAll India NCERT Mock Test Series is now live!Take Free Test
| Exercise end-of-chapter

Q3: Write an algorithm prime(n) to check if nn is prime. Hint: A prime number pp has exactly two distinct factors, 11 and pp. Can you make use of divisors(n) to write out prime(n)?

UNDERSTAND THE QUESTION

  • The question asks to write an algorithm (a step-by-step procedure) named prime(n) to determine if a given number nn is a prime number.
  • Concept: A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.
  • Logic: We can check if nn is prime by finding all its divisors. If the count of divisors is exactly 2, then nn is prime; otherwise, it is not.

Step 1 — DEFINE THE ALGORITHM STRUCTURE

We define a function prime(n) that takes an integer nn as input and returns True if nn is prime, and False otherwise.

Algorithm prime(n)

  1. Input: An integer nn.
  2. Output: True if nn is prime, False otherwise.

Step 2 — HANDLE BASE CASES

By definition, a prime number must be greater than 1.

  • If n≤1n \le 1, then nn is not prime. Return False.
  • If n=2n = 2, it is the smallest prime number. Return True.

This step ensures we only process numbers n>1n > 1 in the subsequent steps.

Step 3 — CHECK FOR DIVISORS

We need to check if nn has any divisors other than 1 and nn itself.

  • Initialize a flag isPrime to True.
  • Iterate through integers ii from 2 to n−1n-1.
  • For each ii, check if nn is divisible by ii (i.e., if nmod  i=0n \mod i = 0).
  • If nn is divisible by any ii in this range, then nn has a divisor other than 1 and itself. Set isPrime to False and stop the loop.

Note: A more efficient method (often taught in Class 9 computer science or mathematics logic) is to check divisors only up to n\sqrt{n}. However, the basic definition-based algorithm checks up to n−1n-1. For a standard Class 9 algorithm, checking up to n−1n-1 is conceptually simpler and directly follows the definition of divisors.

Step 4 — RETURN THE RESULT

After checking all potential divisors:

  • If isPrime is still True, it means no divisors were found between 2 and n−1n-1. Thus, nn is prime. Return True.
  • If isPrime was set to False, return False.

ANSWER

Algorithm prime(n)

  1. Input: Integer nn
  2. If n≤1n \le 1, return False
  3. If n=2n = 2, return True
  4. Set isPrime = True
  5. For ii from 2 to n−1n-1:
    • If nmod  i=0n \mod i = 0:
  • Set isPrime = False
  • Break the loop
  1. Return isPrime

COMMON MISTAKES

  • Forgetting n=2n=2: Students often forget that 2 is a prime number and might incorrectly classify it as non-prime if the loop starts from 2 and checks divisibility by 2 (since 2mod  2=02 \mod 2 = 0). The base case for n=2n=2 must be handled separately or the loop must start from 3 for even numbers, but the simplest correct approach is to handle n≤1n \le 1 and n=2n=2 explicitly.
  • Loop Range: The loop should run from 2 to n−1n-1. If it runs to nn, it will always find nn as a divisor, making every number non-prime.
  • Definition of Prime: Remember that 1 is not a prime number because it has only one divisor (itself), not two.

Was this solution helpful?

Quick Concept Check: Test Your Understanding

Interactive self-testing widget

?
In the algorithm prime(n), why do we check if n≤1n \le 1 first?