Check if Number is Prime in DSA C#

Mental Model

A prime number is a number greater than 1 that has no divisors other than 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 without leftovers. If you can only split them into one big group or all individually, the number of candies is prime.

Number: 7
Try dividing by: 2, 3, 4, 5, 6
No exact division -> 7 is prime

Dry Run Walkthrough

Input: Check if number 7 is prime

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

Step 1: Check division by 2

7 % 2 != 0 -> no divisor found

Why: 2 is the smallest prime to test divisibility

Step 2: Next divisor candidate: 3

3 > sqrt(7) ≈ 2.64 -> stop, no divisor found

Why: Only test up to square root

Step 3: Stop checking because 3 > sqrt(7) ≈ 2.64

No divisors found up to sqrt(7)

Why: No need to check beyond square root for efficiency

Result:

7 is prime

Annotated Code

DSA C#

using System;

class PrimeChecker
{
    public static bool IsPrime(int number)
    {
        if (number <= 1) return false; // numbers <=1 are not prime
        int limit = (int)Math.Sqrt(number); // only check up to sqrt(number)
        for (int i = 2; i <= limit; i++)
        {
            if (number % i == 0) return false; // divisor found, not prime
        }
        return true; // no divisors found, prime
    }

    static void Main()
    {
        int number = 7;
        bool result = IsPrime(number);
        Console.WriteLine(result ? $"{number} is prime" : $"{number} is not prime");
    }
}

if (number <= 1) return false; // numbers <=1 are not prime

handle numbers that are not prime by definition

int limit = (int)Math.Sqrt(number); // only check up to sqrt(number)

limit divisor checks to square root for efficiency

for (int i = 2; i <= limit; i++)

iterate through possible divisors from 2 to sqrt(number)

if (number % i == 0) return false; // divisor found, not prime

if divisible by i, number is not prime

return true; // no divisors found, prime

if no divisors found, number is prime

Output

7 is prime

Complexity Analysis

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

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach checks all numbers up to n-1 with O(n) time, this method is faster by limiting checks to √n

Edge Cases

number = 1

returns false because 1 is not prime

DSA C#

if (number <= 1) return false; // numbers <=1 are not prime

number = 2

returns true because 2 is the smallest prime

DSA C#

for (int i = 2; i <= limit; i++)

number = 0 or negative

returns false because primes are positive integers greater than 1

DSA C#

if (number <= 1) return false; // numbers <=1 are not prime

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 divisibility up to the square root.

Common Mistakes

Mistake: Checking divisibility up to number-1 instead of square root
Fix: Limit divisor checks to square root of the number for efficiency

Mistake: Not handling numbers less than or equal to 1
Fix: Add a condition to return false for numbers <= 1

Summary

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

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

Only check divisors up to the square root because larger divisors would have smaller complementary divisors already checked.

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