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.