Check if Number is Prime in DSA C# - Time & Space Complexity

Time Complexity: Check if Number is Prime

O(√n)

Understanding Time Complexity

We want to understand how the time to check if a number is prime grows as the number gets bigger.

How many steps does it take to decide if a number has no divisors other than 1 and itself?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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;
}
    

This code checks if a number is prime by testing divisors from 2 up to the square root of the number.

Identify Repeating Operations

• Primary operation: The for-loop checking divisors from 2 to √n.
• How many times: Approximately √n times in the worst case.

How Execution Grows With Input

As the number n grows, the number of divisor checks grows roughly with the square root of n.

Input Size (n)	Approx. Operations
10	About 3 checks (2 to 3)
100	About 10 checks (2 to 10)
1000	About 31 checks (2 to 31)

Pattern observation: The number of steps grows slower than n, closer to the square root of n.

Final Time Complexity

Time Complexity: O(√n)

This means the time to check if a number is prime grows roughly with the square root of the number.

Common Mistake

[X] Wrong: "We need to check all numbers from 2 up to n-1 to find if n is prime."

[OK] Correct: Checking up to n-1 is unnecessary because any factor larger than √n would have a matching smaller factor already checked.

Interview Connect

Understanding this time complexity helps you explain efficient prime checks and shows you can optimize simple loops, a skill valued in many coding challenges.

Self-Check

"What if we changed the loop to check divisors up to n/2 instead of √n? How would the time complexity change?"

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