Check if Number is Prime in DSA Java

Mental Model

A prime number is only divisible by 1 and itself. To check if a number is prime, test if any smaller number divides it evenly.

Analogy: Imagine you have a group of identical candies and want to split them evenly into smaller groups. If you can only split them into one big group or all single candies, the number of candies is prime.

Number: 7
Divisors tested: 2, 3
7 is prime if none divide it evenly

7
↑
Check divisors -> 2, 3
No divisor divides 7 evenly

Dry Run Walkthrough

Input: Check if 7 is prime

Goal: Determine if 7 has any divisors other than 1 and 7

Step 1: Check if 7 is less than 2

7 (number to check)
No action needed since 7 >= 2

Why: Numbers less than 2 are not prime

Step 2: Test divisor 2: 7 % 2 != 0

Divisor 2 does not divide 7 evenly

Why: If any divisor divides evenly, number is not prime

Step 3: Test divisor 3: 7 % 3 != 0

Divisor 3 does not divide 7 evenly

Why: Continue testing divisors up to sqrt(7)

Step 4: No divisors found, conclude 7 is prime

7 is prime

Why: No divisor other than 1 and 7 divides it evenly

Result:

7 is prime

Annotated Code

DSA Java

public class PrimeCheck {
    // Function to check if a number is prime
    public static boolean isPrime(int n) {
        if (n < 2) return false; // Numbers less than 2 are not prime
        for (int i = 2; i * i <= n; i++) { // Test divisors up to sqrt(n)
            if (n % i == 0) return false; // Found a divisor, not prime
        }
        return true; // No divisors found, number is prime
    }

    public static void main(String[] args) {
        int number = 7; // Input number to check
        if (isPrime(number)) {
            System.out.println(number + " is prime");
        } else {
            System.out.println(number + " is not prime");
        }
    }
}

if (n < 2) return false; // Numbers less than 2 are not prime

Exclude numbers less than 2 as they are not prime

for (int i = 2; i * i <= n; i++) { // Test divisors up to sqrt(n)

Check divisors from 2 up to square root of n to reduce checks

if (n % i == 0) return false; // Found a divisor, not prime

If any divisor divides n evenly, n is not prime

return true; // No divisors found, number is prime

If no divisors found, n is prime

Output

7 is prime

Complexity Analysis

Time: O(√n) because we only check divisors up to the square root of n

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Naive approach checks all numbers up to n-1 with O(n) time, which is slower than O(√n)

Edge Cases

Number less than 2 (e.g., 0 or 1)

Function returns false immediately as these are not prime

DSA Java

if (n < 2) return false; // Numbers less than 2 are not prime

Number is 2 (smallest prime)

Function returns true since 2 is prime

DSA Java

for (int i = 2; i * i <= n; i++) { ... }

Large prime number (e.g., 29)

Function correctly tests divisors up to sqrt(29) and returns true

DSA Java

for (int i = 2; i * i <= n; i++) { ... }

When to Use This Pattern

When you need to check if a number has no divisors other than 1 and itself, use the prime check pattern by testing divisors up to the square root.

Common Mistakes

Mistake: Checking divisors up to n-1 instead of sqrt(n), causing unnecessary work
Fix: Only check divisors up to the square root of n to optimize performance

Mistake: Not handling numbers less than 2, incorrectly marking them as prime
Fix: Add a condition to return false for numbers less than 2

Summary

Checks if a number is prime by testing divisors up to its square root.

Use when you need to quickly determine if a number has no divisors other than 1 and itself.

The key insight is that you only need to test divisors up to the square root of the number.

Practice

1. What does it mean for a number to be prime?

easy

A. It has exactly two distinct positive divisors: 1 and itself.

B. It is divisible by 2 only.

C. It is an even number greater than 2.

D. It has more than two divisors.

Solution

1. Step 1: Understand the definition of prime number

   A prime number is a number greater than 1 that has no divisors other than 1 and itself.

2. Step 2: Compare options with definition

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states that prime numbers have exactly two distinct positive divisors: 1 and itself.

3. Final Answer:

   It has exactly two distinct positive divisors: 1 and itself. -> Option A

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime numbers have only 1 and itself as divisors [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Assuming 1 is prime

2. Which of the following Java code snippets correctly checks if a number n is prime?

easy

A. for (int i = 2; i < n / 2; i++) { if (n % i == 0) return true; } return false;

B. for (int i = 2; i <= n; i++) { if (n % i == 0) return false; } return true;

C. for (int i = 1; i < n; i++) { if (n % i == 0) return false; } return true;

D. for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true;

Solution

1. Step 1: Analyze the loop range for checking divisors

   We check divisors from 2 up to but not including n to see if n is divisible by any number other than 1 and itself.

2. Step 2: Check each option's logic

   for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; correctly loops from 2 to n-1 and returns false if a divisor is found, else true. for (int i = 2; i <= n; i++) { if (n % i == 0) return false; } return true; incorrectly includes n itself, causing false negatives. for (int i = 1; i < n; i++) { if (n % i == 0) return false; } return true; starts from 1, which divides all numbers. for (int i = 2; i < n / 2; i++) { if (n % i == 0) return true; } return false; returns true on finding a divisor but should return false.

3. Final Answer:

   for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; -> Option D

4. Quick Check:

   Loop 2 to n-1 and check divisibility [OK]

Hint: Loop from 2 to n-1 to check divisors [OK]

Common Mistakes:

• Checking divisibility including n itself
• Starting loop from 1 instead of 2
• Returning true when divisor found

3. What is the output of the following Java code when n = 11?

boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
System.out.println(isPrime);

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand the loop range and condition

   The loop runs from 2 to the square root of 11 (approximately 3.3), so i takes values 2 and 3.

2. Step 2: Check divisibility for i=2 and i=3

   11 % 2 != 0 and 11 % 3 != 0, so no divisor found, isPrime remains true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime, so output is true [OK]

Hint: Check divisors only up to sqrt(n) for efficiency [OK]

Common Mistakes:

• Looping up to n instead of sqrt(n)
• Forgetting to break loop on divisor found
• Misunderstanding boolean flag usage

4. Find the error in the following Java code that checks if n is prime:

boolean isPrime = true;
for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) {
        isPrime = true;
        break;
    }
}
System.out.println(isPrime);

medium

A. The loop should run until i < n, not n / 2.

B. The flag isPrime should be set to false when divisor found, not true.

C. The loop variable i should start from 1, not 2.

D. There is no error; the code works correctly.

Solution

1. Step 1: Analyze the flag update inside the loop

   When a divisor is found, isPrime should be set to false, but here it is incorrectly set to true.

2. Step 2: Check loop range and starting point

   The loop from 2 to n/2 is acceptable for checking divisors, so no error there.

3. Final Answer:

   The flag isPrime should be set to false when divisor found, not true. -> Option B

4. Quick Check:

   Set isPrime = false on divisor found [OK]

Hint: Set prime flag false when divisor found [OK]

Common Mistakes:

• Setting isPrime true inside divisor check
• Looping from 1 instead of 2
• Ignoring break after finding divisor

5. You want to write a Java method isPrime(int n) that returns true if n is prime and false otherwise. Which of the following improvements makes the method more efficient for large n?

hard

A. Check divisibility by all numbers from 2 to n-1 without any break.

B. Check divisibility only by even numbers.

C. Check divisibility only up to the square root of n instead of n-1.

D. Check divisibility by numbers greater than n/2 only.

Solution

1. Step 1: Understand the divisor checking range

   Any divisor larger than the square root of n would have a corresponding divisor smaller than the square root, so checking beyond sqrt(n) is unnecessary.

2. Step 2: Evaluate options for efficiency

   Check divisibility only up to the square root of n instead of n-1. reduces the number of checks drastically, improving efficiency. Check divisibility by all numbers from 2 to n-1 without any break. is inefficient. Check divisibility only by even numbers. is wrong because even numbers except 2 are not prime. Check divisibility by numbers greater than n/2 only. misses smaller divisors.

3. Final Answer:

   Check divisibility only up to the square root of n instead of n-1. -> Option C

4. Quick Check:

   Check divisors up to sqrt(n) for efficiency [OK]

Hint: Only check divisors up to sqrt(n) for speed [OK]

Common Mistakes:

• Checking all numbers up to n-1
• Checking only even numbers
• Ignoring divisor pairs below sqrt(n)