Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Check Prime
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Write a Recursive Solution to Check if a Given Number is a Prime Number or Not.

Given a positive integer, we need to determine whether it is a prime number or not. A prime number is a number greater than 1 that has no positive divisors other than 1 and the number itself.

The following table describes three example outputs for three inputs along with the description:

Input(s)Output(s)Explanation
Number = 7Is Prime = trueThe number 7 is only divisible by 1 and 7, so it is a prime number.
Number = 12Is Prime = falseThe number 12 is divisible by 1, 2, 3, 4, 6, and 12, so it is not a prime number.
Number = 23Is Prime = trueThe number 23 is only divisible by 1 and 23, so it is a prime number.

Constraints:

  • 0 <= n <= 10<sup>9</sup>

Solution

The algorithm to check if a number is prime or not using recursion can be defined as follows:

  1. If the number is less than 2, return false (base case).
  2. If the number is equal to 2, return true (base case).
  3. If the number is divisible by any number from 2 to the square root of the number, return false.
  4. Otherwise, return true.

The recursive approach works by checking if the number has any divisors from 2 to its square root. If it does, the number is not prime. If no divisors are found, the number is prime.

Example Dry run to check if 11 is a prime number or not
Example Dry run to check if 11 is a prime number or not

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time and Space Complexity

The time complexity of the algorithm is O(sqrt(N)), where N is the given number. This is because the algorithm checks the divisibility of the number up to its square root. The space complexity is O(sqrt(N)) as well, as the maximum depth of the recursion is determined by the square root of the number.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible