Q3: Write an algorithm prime(n) to check if is prime.
Hint: A prime number has exactly two distinct factors, and . Can you make use of divisors(n) to write out prime(n)?
SOLUTION
UNDERSTAND THE QUESTION
- The question asks to write an algorithm (a step-by-step procedure) named
prime(n)to determine if a given number 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 is prime by finding all its divisors. If the count of divisors is exactly 2, then is prime; otherwise, it is not.
Step 1 — DEFINE THE ALGORITHM STRUCTURE
We define a function prime(n) that takes an integer as input and returns True if is prime, and False otherwise.
Algorithm prime(n)
- Input: An integer .
- Output:
Trueif is prime,Falseotherwise.
Step 2 — HANDLE BASE CASES
By definition, a prime number must be greater than 1.
- If , then is not prime. Return
False. - If , it is the smallest prime number. Return
True.
This step ensures we only process numbers in the subsequent steps.
Step 3 — CHECK FOR DIVISORS
We need to check if has any divisors other than 1 and itself.
- Initialize a flag
isPrimetoTrue. - Iterate through integers from 2 to .
- For each , check if is divisible by (i.e., if ).
- If is divisible by any in this range, then has a divisor other than 1 and itself. Set
isPrimetoFalseand 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 . However, the basic definition-based algorithm checks up to . For a standard Class 9 algorithm, checking up to is conceptually simpler and directly follows the definition of divisors.
Step 4 — RETURN THE RESULT
After checking all potential divisors:
- If
isPrimeis stillTrue, it means no divisors were found between 2 and . Thus, is prime. ReturnTrue. - If
isPrimewas set toFalse, returnFalse.
ANSWER
Algorithm prime(n)
- Input: Integer
- If , return
False - If , return
True - Set
isPrime=True - For from 2 to :
- If :
- Set
isPrime=False - Break the loop
- Return
isPrime
COMMON MISTAKES
- Forgetting : 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 ). The base case for must be handled separately or the loop must start from 3 for even numbers, but the simplest correct approach is to handle and explicitly.
- Loop Range: The loop should run from 2 to . If it runs to , it will always find 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.