Solution Check Prime

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 = 7	Is Prime = true	The number 7 is only divisible by 1 and 7, so it is a prime number.
Number = 12	Is Prime = false	The number 12 is divisible by 1, 2, 3, 4, 6, and 12, so it is not a prime number.
Number = 23	Is Prime = true	The number 23 is only divisible by 1 and 23, so it is a prime number.

Constraints:

0 <= n <= 10⁹

Solution

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

If the number is less than 2, return false (base case).
If the number is equal to 2, return true (base case).
If the number is divisible by any number from 2 to the square root of the number, return false.
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

Code

Here is the code for this algorithm:

java

public class Solution {

  public static boolean isPrime(int number) {
    if (number < 2) {
      return false; // Base case 1
    }
    if (number == 2) {
      return true; // Base case 2
    }
    return checkDivisors(number, 2); // Recursive call
  }

  private static boolean checkDivisors(int number, int divisor) {
    if (divisor > Math.sqrt(number)) {
      return true; // Base case 3
    }
    if (number % divisor == 0) {
      return false; // Number is divisible, not prime
    }
    return checkDivisors(number, divisor + 1); // Recursive call
  }

  public static void main(String[] args) {
    // Example inputs
    int[] examples = { 7, 12, 23 };

    for (int example : examples) {
      boolean isPrime = isPrime(example);
      System.out.println(example + " is prime: " + isPrime);
    }
  }
}

Time and Space Complexity

The time complexity of the algorithm is , 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 as well, as the maximum depth of the recursion is determined by the square root of the number.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Check Prime? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Check Prime** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Check Prime** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Check Prime**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Check Prime**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Converting Decimal to Bin Solution Perfect Square →