Check if Number is Prime in DSA Java - Execution Trace

Concept Flow - Check if Number is Prime

Start with number n

↓

Check if n <= 1?

Yes→Not Prime

No↓

Set divisor = 2

↓

Is divisor * divisor <= n?

No→Prime

Yes↓

Check if n % divisor == 0?

Yes→Not Prime

No↓

Increment divisor by 1

↩Back to divisor * divisor <= n check

Start by checking if number is less than or equal to 1 (not prime). Then test divisors from 2 up to sqrt(n). If any divides n exactly, number is not prime; otherwise, it is prime.

Execution Sample

DSA Java

int n = 11;
boolean isPrime = true;
for (int i = 2; i * i <= n; i++) {
  if (n % i == 0) {
    isPrime = false;
    break;
  }
}

Check if 11 is prime by testing divisors from 2 up to sqrt(11).

Execution Table

Step	i	Condition (i*i <= n)	n % i == 0?	isPrime	Action	Reasoning
1	2	4 <= 11 (True)	11 % 2 = 1 (False)	true	Continue	2 does not divide 11 exactly
2	3	9 <= 11 (True)	11 % 3 = 2 (False)	true	Continue	3 does not divide 11 exactly
3	4	16 <= 11 (False)	-	true	Exit loop	4*4 > 11, no divisor found
4	-	-	-	true	Number is Prime	No divisor found up to sqrt(11)

💡 Loop ends when i*i > n; no divisor found, so number is prime.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
i	-	2	3	4	-
isPrime	true	true	true	true	true

Key Moments - 3 Insights

Why do we check i * i <= n instead of i <= n?

Because if n has a divisor larger than sqrt(n), it must have a smaller paired divisor. Checking up to sqrt(n) is enough and saves time, as shown in execution_table rows 1-3.

Why do we break the loop when n % i == 0?

Because finding any divisor means n is not prime. No need to check further. This is shown in the condition check in execution_table row 2.

What if n is less than or equal to 1?

Numbers <= 1 are not prime by definition. The flow in concept_flow shows this initial check before the loop.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i when the loop exits?

A 2

B 3

C 4

D 5

💡 Hint

Check the 'Condition (i*i <= n)' column in step 3 where it becomes false.

At which step does the code confirm the number is prime?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look for the row where the action says 'Number is Prime' in the execution_table.

If n was 9, what would happen at step 2 in the execution_table?

A n % i == 0 would be false

B n % i == 0 would be true

C Loop would exit early

D i would increment to 4

💡 Hint

9 % 3 equals 0, so divisor 3 divides 9 exactly.

Concept Snapshot

Check if number n is prime:
- If n <= 1, not prime
- Test divisors i from 2 to sqrt(n)
- If n % i == 0, not prime
- If no divisors found, prime
- Stop early when divisor found or i*i > n

Full Transcript

To check if a number is prime, first verify if it is greater than 1. Then test all numbers starting from 2 up to the square root of the number. If any of these numbers divides the number exactly, it is not prime. Otherwise, it is prime. The loop stops early if a divisor is found or when the divisor squared exceeds 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)