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

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 the number is less than or equal to 1 (not prime). Then test divisors from 2 up to the square root of the number. If any divisor divides the number evenly, it is not prime; otherwise, it is prime.

Execution Sample

DSA C

int isPrime(int n) {
  if (n <= 1) return 0;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}

This function checks if n is prime by testing divisors from 2 up to sqrt(n). Returns 1 if prime, 0 otherwise.

Execution Table

Step	Operation	Divisor (i)	Condition (i*i <= n)	Check n % i == 0	Result	Reason
1	Check if n <= 1	-	-	-	No	n=11 > 1, continue
2	Set divisor i = 2	2	2*2=4 <= 11	-	-	Start loop
3	Check if 11 % 2 == 0	2	4 <= 11	11 % 2 = 1	No	2 does not divide 11
4	Increment divisor i = 3	3	3*3=9 <= 11	-	-	Continue loop
5	Check if 11 % 3 == 0	3	9 <= 11	11 % 3 = 2	No	3 does not divide 11
6	Increment divisor i = 4	4	4*4=16 <= 11	-	-	Condition false, exit loop
7	Return 1 (Prime)	-	-	-	Yes	No divisors found, 11 is prime

💡 Loop ends when divisor squared exceeds n; no divisor evenly divides n, so n is prime.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
n	11	11	11	11	11
i (divisor)	-	2	3	4	4
Condition i*i <= n	-	True	True	False	False
Result (prime?)	-	-	-	-	1 (True)

Key Moments - 3 Insights

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

Because if n has a divisor larger than its square root, it must have a smaller one too. Checking up to sqrt(n) is enough and saves time, as shown in steps 2, 4, and 6.

Why return 0 immediately when n % i == 0?

Because finding any divisor means n is not prime. The function stops early to save work, as seen in step 3 and 5 where checks happen.

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

The function returns 0 immediately since numbers <= 1 are not prime, as shown in step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the divisor i when the loop condition becomes false?

A 4

B 3

C 2

D 5

💡 Hint

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

At which step does the function confirm that 11 is prime?

A Step 3

B Step 6

C Step 7

D Step 1

💡 Hint

Look for the step where the function returns 1 indicating prime.

If n was 9 instead of 11, at which step would the function return 0?

A Step 3

B Step 5

C Step 7

D Step 2

💡 Hint

Check when n % i == 0 is true for i=3 (since 9 % 3 == 0).

Concept Snapshot

Check if number n is prime:
- If n <= 1, return not prime
- Test divisors i from 2 to sqrt(n)
- If any i divides n evenly, return not prime
- Else, return prime
- Stops early on first divisor found

Full Transcript

This concept checks if a number is prime by testing divisors from 2 up to the square root of the number. It first excludes numbers less than or equal to 1. Then it loops through possible divisors, checking if any divide the number evenly. If yes, it returns not prime immediately. If no divisors are found, it returns prime. The loop condition uses i*i <= n to optimize checks. The execution table traces these steps for n=11, showing divisor values, conditions, and results at each step.

Practice

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

easy

A. It is divisible by 2.

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

C. It is an even number.

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 this definition. Options B, C, and D are incorrect because they describe properties that do not define prime numbers.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

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

Common Mistakes:

• Thinking all even numbers are prime
• Confusing prime with composite numbers
• Including 1 as a prime number

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

easy

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

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

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

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

Solution

1. Step 1: Analyze loop range for divisor checking

   To check if n is prime, we test divisors from 2 up to n-1. for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; uses i < n, which is correct.

2. Step 2: Check return values and conditions

   for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; returns 0 if a divisor is found, else returns 1 meaning prime. Other options have incorrect loop ranges or return values.

3. Final Answer:

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

4. Quick Check:

   Loop from 2 to n-1 and return 0 if divisible [OK]

Hint: Check divisors from 2 to n-1 for prime [OK]

Common Mistakes:

• Checking divisibility by 1
• Looping up to n instead of n-1
• Returning wrong values on divisor found

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

int isPrime(int n) {
  if (n <= 1) return 0;
  for (int i = 2; i < i * i <= n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}

printf("%d", isPrime(n));

medium

A. 1

B. Compilation error

C. 0

D. Infinite loop

Solution

1. Step 1: Analyze the for loop condition

   In C, relational operators (<, <=) associate left-to-right with same precedence. i < i * i <= n parses as (i < (i * i)) <= n. For i ≥ 2, i < i*i is true (1), so 1 <= n is true. Condition always true.

2. Step 2: Runtime behavior

   Loop never terminates (infinite loop). No printf output.

3. Final Answer:

   Infinite loop -> Option D

4. Quick Check:

   (i < i*i) <= n always true [OK]

Hint: C relational ops left-to-right: (i < i*i) <= n always true [OK]

Common Mistakes:

• Thinking chained comparisons cause compile error
• Assuming Python-like chained comparison
• Believing loop stops at sqrt(n)

4. Find the error in this C function to check if n is prime:

int isPrime(int n) {
  if (n <= 1) return 0;
  for (int i = 2; i <= n / 2; i++) {
    if (n % i = 0) return 0;
  }
  return 1;
}

medium

A. Using assignment operator '=' instead of comparison '==' in if condition

B. Loop should run till i < n, not n / 2

C. Missing return statement at the end

D. No error, code is correct

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses n % i = 0 which is assignment, not comparison.

2. Step 2: Understand impact of assignment in condition

   This causes a syntax error or unintended behavior. It should be n % i == 0 to compare.

3. Final Answer:

   Using assignment operator '=' instead of comparison '==' in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, '=' assigns value [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Looping till n/2 is actually correct optimization
• Ignoring compiler error messages

5. You want to optimize prime checking for large n. Which change improves efficiency the most?

int isPrime(int n) {
  if (n <= 1) return 0;
  for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}

hard

A. Change loop to run till i * i <= n instead of i <= n / 2

B. Check divisibility only by even numbers

C. Start loop from 1 instead of 2

D. Remove the initial check for n <= 1

Solution

1. Step 1: Understand loop optimization for prime checking

   Checking divisors up to n/2 is inefficient. We only need to check up to the square root of n.

2. Step 2: Apply loop condition using i * i <= n

   Changing the loop to run while i * i <= n reduces iterations and improves efficiency.

3. Final Answer:

   Change loop to run till i * i <= n instead of i <= n / 2 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Checking even numbers only misses odd divisors
• Starting loop from 1 wastes time
• Removing base case causes wrong results