Check if Number is Prime in DSA C# - Execution Trace

Concept Flow - Check if Number is Prime

Start with number n

↓

Check if n <= 1?

Yes→Not Prime, Stop

No↓

Set divisor = 2

↓

Is divisor * divisor <= n?

No→Prime, Stop

Yes↓

Check if n % divisor == 0?

Yes→Not Prime, Stop

No↓

Increment divisor by 1

↩Back to divisor * divisor <= n check

Start by checking if the number is less than or equal to 1. If yes, it is not prime. Otherwise, test divisors from 2 up to the square root of the number. If any divisor divides the number evenly, it is not prime. If none do, it is prime.

Execution Sample

DSA C#

bool IsPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

This code checks if a number n is prime by testing divisors from 2 up to sqrt(n).

Execution Table

Step	Operation	Divisor (i)	Condition i*i <= n	n % i == 0?	Result	Reasoning
1	Check if n <= 1	-	-	-	False	n=17 > 1, continue
2	Set divisor i = 2	2	2*2=4 <= 17 True	-	-	Start divisor check
3	Check if 17 % 2 == 0	2	True	False	Continue	2 does not divide 17
4	Increment divisor i = 3	3	3*3=9 <= 17 True	-	-	Next divisor
5	Check if 17 % 3 == 0	3	True	False	Continue	3 does not divide 17
6	Increment divisor i = 4	4	4*4=16 <= 17 True	-	-	Next divisor
7	Check if 17 % 4 == 0	4	True	False	Continue	4 does not divide 17
8	Increment divisor i = 5	5	5*5=25 <= 17 False	-	-	Stop loop, no divisor found
9	Return True	-	-	-	True	No divisor found, 17 is prime

💡 Loop ends when divisor squared exceeds n; no divisor found means n is prime.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
n	17	17	17	17	17	17
i (divisor)	-	2	3	4	5	5
Condition i*i <= n	-	True	True	True	False	False
n % i == 0	-	False	False	False	-	-
Result	-	-	-	-	-	True (prime)

Key Moments - 3 Insights

Why do we check divisors only up to i*i <= n instead of i <= n?

Because if n has a divisor larger than its square root, it must have a smaller corresponding divisor. Checking up to sqrt(n) is enough to find any divisor. See execution_table rows 2, 6, and 8.

Why do we return false immediately when n % i == 0?

Because finding any divisor means n is not prime. No need to check further. This is shown in execution_table row 3 where the check fails and continues, but if it was true, we would stop.

What happens if n is less than or equal to 1?

The function returns false immediately because numbers less than or equal to 1 are not prime. This is shown in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the divisor i when the loop stops?

A 5

B 4

C 6

D 3

💡 Hint

Check the divisor value in execution_table row 8 where the condition i*i <= n becomes false.

At which step does the code confirm that 17 is prime?

A Step 7

B Step 9

C Step 8

D Step 3

💡 Hint

Look for the step where the function returns true in the execution_table.

If n was 15, at which divisor would the function return false?

A 4

B 2

C 3

D 5

💡 Hint

Check when n % i == 0 would be true for n=15; 15 % 3 == 0.

Concept Snapshot

Check if number n is prime:
- If n <= 1, return false
- For i from 2 to sqrt(n):
  - If n % i == 0, return false
- If no divisor found, return true
Use i*i <= n for efficiency.

Full Transcript

To check if a number is prime, first verify if it is greater than 1. Then test divisors starting from 2 up to the square root of the number. If any divisor divides the number evenly, the number is not prime. If no divisors are found, the number is prime. This method reduces checks by stopping at the square root because any larger divisor would have a smaller pair already checked. The code returns false immediately upon finding a divisor, and true if none are found. This approach is efficient and commonly used.

Practice

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

easy

A. It is an even number greater than 2.

B. It is divisible by 2 only.

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

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

   It has exactly two distinct positive divisors: 1 and itself. matches this definition exactly, while others do not.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime means only divisible by 1 and itself [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Believing prime numbers have multiple divisors

2. Which of the following C# 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 false; } return true;

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

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

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

Solution

1. Step 1: Analyze the loop range and condition

   for (int i = 2; i <= n / 2; i++) { if (n % i == 0) return false; } return true; checks divisors from 2 up to n/2, which is sufficient to find factors for primality.

2. Step 2: Check the modulo condition and return values

   for (int i = 2; i <= n / 2; i++) { if (n % i == 0) return false; } return true; returns false if a divisor is found, otherwise true, correctly identifying primes.

3. Final Answer:

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

4. Quick Check:

   Loop 2 to n/2 and check divisibility [OK]

Hint: Check divisors from 2 to n/2 for efficiency [OK]

Common Mistakes:

• Starting loop from 1 instead of 2
• Checking modulo equals 1 instead of 0
• Returning true inside the loop incorrectly

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

bool IsPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= Math.Sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}
Console.WriteLine(IsPrime(11));

medium

A. False

B. Runtime error

C. Compile error

D. True

Solution

1. Step 1: Understand the prime check logic

   The function returns false if n <= 1, else checks divisors from 2 to sqrt(n). For 11, sqrt(11) ~ 3.3, so loop checks i=2,3.

2. Step 2: Check divisibility for n=11

   11 % 2 != 0 and 11 % 3 != 0, so loop completes without returning false, function returns true.

3. Final Answer:

   True -> Option D

4. Quick Check:

   11 is prime, so output is True [OK]

Hint: Check divisors only up to square root [OK]

Common Mistakes:

• Not using Math.Sqrt and checking too many numbers
• Returning false for prime numbers
• Confusing output with string instead of boolean

4. Identify the error in this C# code snippet for checking if n is prime:

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

medium

A. Loop should use <= instead of < to include n/2

B. Check for n <= 1 should be after the loop

C. Return true should be inside the loop

D. Loop should run up to Math.Sqrt(n) for efficiency

Solution

1. Step 1: Test with n=4

   n/2 = 2 (integer division), loop i=2 < 2 is false, loop skipped, returns true incorrectly (4 is not prime).

2. Step 2: Identify the fix

   Change to i <= n/2 includes i=2 when n/2=2, checking 4 % 2 == 0 and returning false.

3. Final Answer:

   Loop should use <= instead of < to include n/2 -> Option A

4. Quick Check:

   For n=4, i <= n/2 checks divisor 2 [OK]

Hint: Use <= n/2 to include boundary divisor check [OK]

Common Mistakes:

• Using < instead of <= for loop upper bound
• Returning true inside the loop prematurely
• Checking n <= 1 after the loop

5. You want to check if a large number n is prime efficiently. Which approach below is best to implement in C#?

hard

A. Check divisibility from 2 to n-1 using a for loop

B. Check divisibility from 2 to Math.Sqrt(n) using a for loop

C. Check divisibility from 2 to n/2 using a for loop

D. Check divisibility only by 2 and 3

Solution

1. Step 1: Understand the efficiency of divisor checking

   Checking all numbers up to n-1 or n/2 is slow for large n.

2. Step 2: Use mathematical property to limit checks

   Any factor larger than sqrt(n) pairs with a smaller factor, so checking up to sqrt(n) suffices.

3. Step 3: Evaluate options

   Check divisibility from 2 to Math.Sqrt(n) using a for loop uses sqrt(n) limit, which is efficient and correct. Check divisibility only by 2 and 3 is incomplete as primes can have other factors.

4. Final Answer:

   Check divisibility from 2 to Math.Sqrt(n) using a for loop -> Option B

5. Quick Check:

   Use sqrt(n) limit for best prime check [OK]

Hint: Limit divisor checks to square root of number [OK]

Common Mistakes:

• Checking too many numbers causing slow code
• Only checking 2 and 3 misses other factors
• Not handling edge cases like n <= 1