Check if Number is Prime in DSA Go - 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 check

Start from 2 and check divisors up to sqrt(n). If any divides n, it's not prime; else it is.

Execution Sample

DSA Go

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

Checks if 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	Reason/Action
1	Check if n <= 1	-	-	-	false	n=29 > 1, continue
2	Initialize divisor i	2	2*2=4 <= 29	-	-	Start loop with i=2
3	Check divisibility	2	4 <= 29	29 % 2 = 1	false	Not divisible, increment i
4	Increment divisor	3	3*3=9 <= 29	-	-	Continue loop with i=3
5	Check divisibility	3	9 <= 29	29 % 3 = 2	false	Not divisible, increment i
6	Increment divisor	4	4*4=16 <= 29	-	-	Continue loop with i=4
7	Check divisibility	4	16 <= 29	29 % 4 = 1	false	Not divisible, increment i
8	Increment divisor	5	5*5=25 <= 29	-	-	Continue loop with i=5
9	Check divisibility	5	25 <= 29	29 % 5 = 4	false	Not divisible, increment i
10	Increment divisor	6	6*6=36 > 29	-	-	Condition false, exit loop
11	Return result	-	-	-	true	No divisor found, n 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	After Step 10	Final
n	29	29	29	29	29	29	29
i (divisor)	-	2	3	4	5	6	-
Condition i*i <= n	-	true	true	true	true	false	-
n % i == 0	-	false	false	false	false	-	-

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 one too. Checking up to sqrt(n) is enough and saves time (see execution_table rows 2, 10).

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

If n is divisible by i, it means n is not prime. No need to check further (see execution_table row 3).

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

Numbers <= 1 are not prime by definition, so we return false immediately (see execution_table row 1).

Visual Quiz - 3 Questions

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

A 5

B 6

C 7

D 4

💡 Hint

Check the 'Condition i*i <= n' column in row 10 where it becomes false.

At which step does the function decide that 29 is prime?

A Step 11

B Step 9

C Step 10

D Step 3

💡 Hint

Look at the 'Result' and 'Reason/Action' columns in the last step.

If n was 25 instead of 29, at which divisor i would the function return false?

A 3

B 4

C 5

D 6

💡 Hint

Check when n % i == 0 would be true for 25; 25 % 5 == 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
Efficiently checks divisors only up to sqrt(n).

Full Transcript

This concept checks if a number n is prime by testing divisors from 2 up to the square root of n. If n is less than or equal to 1, it is not prime. The function loops through possible divisors i, checking if i squared is less than or equal to n. If n is divisible by any i, it returns false immediately. If the loop finishes without finding a divisor, the function returns true, confirming n is prime. The execution table shows each step, divisor, condition checks, and results for n=29. Key moments clarify why we check up to sqrt(n), why we return false on first divisor found, and why numbers <= 1 are not prime.

Practice

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

easy

A. It has more than two divisors.

B. It is divisible by 2 only.

C. It is an even number greater than 2.

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

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 describe incorrect properties.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors only [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 1 is prime

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

easy

A. for i := 2; i < n; i++ { if n%i == 0 { return false } } return true

B. for i := 2; i <= n; i++ { if n%i == 0 { return false } } return true

C. for i := 1; i < n; i++ { if n%i == 0 { return false } } return true

D. for i := 2; i < n/2; i++ { if n%i == 0 { return true } } return false

Solution

1. Step 1: Analyze loop range for prime check

   We check divisors from 2 up to but not including n to find if n is divisible by any number other than 1 and itself.

2. Step 2: Evaluate each option's correctness

   for i := 2; i < n; i++ { if n%i == 0 { return false } } return true correctly loops from 2 to n-1 and returns false if divisible. for i := 2; i <= n; i++ { if n%i == 0 { return false } } return true incorrectly includes n itself, always returning false. for i := 1; i < n; i++ { if n%i == 0 { return false } } return true starts from 1, which divides all numbers. for i := 2; i < n/2; i++ { if n%i == 0 { return true } } return false returns true on divisor found, which is wrong logic.

3. Final Answer:

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

4. Quick Check:

   Loop 2 to n-1 and check divisibility [OK]

Hint: Loop from 2 to n-1, return false if divisible [OK]

Common Mistakes:

• Checking divisibility including n itself
• Starting loop from 1 instead of 2
• Returning true when divisor found

3. What will be the output of this Go function call: isPrime(11)?

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

medium

A. true

B. false

C. runtime error

D. infinite loop

Solution

1. Step 1: Check input and loop condition

   Input n=11 is greater than 1, so function proceeds. Loop runs from i=2 while i*i <= 11 (i <= 3).

2. Step 2: Test divisibility inside loop

   Check i=2: 11%2 != 0; i=3: 11%3 != 0. No divisor found, loop ends.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime, function returns true [OK]

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

Common Mistakes:

• Not handling n <= 1 correctly
• Looping beyond sqrt(n)
• Assuming 11 is not prime

4. Identify the bug in this Go function that checks if a number is prime:

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

medium

A. Loop should run until i <= n, not i < n/2

B. Function should return true if n <= 1

C. Loop should run until i*i <= n for efficiency and correctness

D. The modulo operator % is used incorrectly

Solution

1. Step 1: Analyze loop range and condition

   The loop runs from 2 to less than n/2, which is inefficient and may miss divisors for small n.

2. Step 2: Suggest correct loop condition

   Looping until i*i <= n is both correct and efficient because any divisor larger than sqrt(n) pairs with a smaller divisor already checked.

3. Final Answer:

   Loop should run until i*i <= n for efficiency and correctness -> Option C

4. Quick Check:

   Use i*i <= n to check divisors [OK]

Hint: Check divisors up to sqrt(n) to fix bugs [OK]

Common Mistakes:

• Looping only to n/2 misses some divisors
• Returning true for n <= 1
• Misusing modulo operator

5. You want to find all prime numbers up to 20 using Go. Which approach is best to optimize performance?

hard

A. Check divisibility for each number up to n-1 without optimization

B. Check each number from 2 to 20 using a function that tests divisibility up to sqrt(n)

C. Use a loop from 2 to 20 and mark all numbers as prime without checks

D. Only check even numbers for primality since odd numbers are not prime

Solution

1. Step 1: Understand prime checking for multiple numbers

   Checking each number from 2 to 20 individually is necessary to find all primes.

2. Step 2: Optimize divisibility checks

   Testing divisibility only up to sqrt(n) for each number reduces unnecessary checks and improves performance.

3. Final Answer:

   Check each number from 2 to 20 using a function that tests divisibility up to sqrt(n) -> Option B

4. Quick Check:

   Use sqrt(n) limit for each number check [OK]

Hint: Test divisibility up to sqrt(n) for each number [OK]

Common Mistakes:

• Checking all numbers up to n-1 wastes time
• Ignoring odd numbers which can be prime
• Marking all numbers prime without checks