Why Check if Number is Prime in DSA Java?

The Big Idea

What if you could check if a number is prime without testing every single smaller number?

The Scenario

Imagine you want to find out if a number is prime by checking every single number smaller than it one by one. For example, to check if 29 is prime, you try dividing it by 2, 3, 4, 5, and so on until 28.

The Problem

This manual method is very slow and tiring, especially for big numbers. It wastes time checking many unnecessary numbers and can easily lead to mistakes or missed checks.

The Solution

Using a simple rule, we only check divisors up to the square root of the number. This cuts down the work drastically and makes the process fast and reliable.

Before vs After

✗ Before

boolean isPrime(int number) {
  for (int i = 2; i < number; i++) {
    if (number % i == 0) return false;
  }
  return true;
}

✓ After

boolean isPrime(int number) {
  if (number <= 1) return false;
  for (int i = 2; i * i <= number; i++) {
    if (number % i == 0) return false;
  }
  return true;
}

What It Enables

This method enables quick and efficient prime checks even for very large numbers, making many math and computer problems easier to solve.

Real Life Example

Prime checking is used in cryptography to create secure keys that protect your online data and communications.

Key Takeaways

Manual checking every number is slow and error-prone.

Checking only up to the square root speeds up the process.

Efficient prime checks are important for security and math problems.

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)