Check if Number is Prime in DSA Go

Mental Model

A prime number is only divisible by 1 and itself. To check if a number is prime, we try dividing it by smaller numbers to see if any divide evenly.

Analogy: Imagine you have a group of identical candies and want to split them evenly into smaller groups. If you can only split them into one big group or all alone, the number of candies is prime.

Number n
  ↓
Check divisors from 2 up to √n
  ↓
If none divide n evenly -> prime
Else -> not prime

Dry Run Walkthrough

Input: Check if 11 is prime

Goal: Determine if 11 has any divisors other than 1 and 11

Step 1: Check if 11 is less than 2 (not prime if yes)

n=11, divisor=2

Why: Numbers less than 2 are not prime

Step 2: Check if 11 divisible by 2

n=11, divisor=2

Why: 2 is the smallest possible divisor to test

Step 3: 2 does not divide 11 evenly, increase divisor to 3

n=11, divisor=3

Why: Try next divisor to find any factor

Step 4: Check if 11 divisible by 3

n=11, divisor=3

Why: Continue checking divisors up to √11

Step 5: 3 does not divide 11 evenly, increase divisor to 4

n=11, divisor=4

Why: Try next divisor

Step 6: Since 4 > √11 (~3.3), stop checking

n=11, divisor=4

Why: No divisors found, so 11 is prime

Result:

11 is prime

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

func isPrime(n int) bool {
	if n < 2 {
		return false // numbers less than 2 are not prime
	}
	limit := int(math.Sqrt(float64(n)))
	for divisor := 2; divisor <= limit; divisor++ {
		if n%divisor == 0 {
			return false // found a divisor, not prime
		}
	}
	return true // no divisors found, prime
}

func main() {
	number := 11
	if isPrime(number) {
		fmt.Printf("%d is prime\n", number)
	} else {
		fmt.Printf("%d is not prime\n", number)
	}
}

if n < 2 { return false }

exclude numbers less than 2 as not prime

limit := int(math.Sqrt(float64(n)))

calculate upper bound for divisor checks

for divisor := 2; divisor <= limit; divisor++ {

iterate through possible divisors up to sqrt(n)

if n%divisor == 0 { return false }

if divisor divides n evenly, n is not prime

return true

no divisors found, n is prime

Output

11 is prime

Complexity Analysis

Time: O(√n) because we only check divisors up to the square root of n

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Checking all numbers up to n would be O(n), so this method is faster by reducing checks to √n

Edge Cases

n = 0 or 1

Returns false because numbers less than 2 are not prime

DSA Go

if n < 2 { return false }

n = 2

Returns true because 2 is the smallest prime number

DSA Go

for divisor := 2; divisor <= limit; divisor++ { ... }

n is a perfect square (e.g., 9)

Detects divisor equal to sqrt(n) and returns false

DSA Go

if n%divisor == 0 { return false }

When to Use This Pattern

When you need to check if a number has no divisors other than 1 and itself, use the prime check pattern by testing divisors up to the square root.

Common Mistakes

Mistake: Checking divisors up to n-1 instead of √n, causing unnecessary work
Fix: Limit divisor checks to the integer square root of n

Mistake: Not handling numbers less than 2 correctly, returning true for 0 or 1
Fix: Add a condition to return false if n < 2

Summary

Checks if a number is prime by testing divisors up to its square root.

Use when you need to quickly determine if a number has factors other than 1 and itself.

Only check divisors up to √n because any larger divisor would have a smaller paired divisor already checked.

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