Check if Number is Prime in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prime Check for 29

What is the output of the following C# code that checks if 29 is prime?

DSA C#

using System;
class Program {
  static bool IsPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
  static void Main() {
    Console.WriteLine(IsPrime(29));
  }
}

A True

B False

C Compile error

D Runtime error

💡 Hint

29 is a prime number because it has no divisors other than 1 and itself.

The code checks divisors from 2 up to sqrt(29). Since none divide 29 evenly, it returns true.

❓ Predict Output

intermediate

Output of Prime Check for 1

What is the output of this C# code when checking if 1 is prime?

DSA C#

using System;
class Program {
  static bool IsPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
  static void Main() {
    Console.WriteLine(IsPrime(1));
  }
}

A True

B Runtime error

C Compile error

D False

💡 Hint

Numbers less than or equal to 1 are not prime.

The code returns false immediately for n <= 1.

❓ Predict Output

advanced

Output of Prime Check for 1000003

What is the output of this C# code when checking if 1000003 is prime?

DSA C#

using System;
class Program {
  static bool IsPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
  static void Main() {
    Console.WriteLine(IsPrime(1000003));
  }
}

A True

B False

C Runtime error due to overflow

D Compile error

💡 Hint

1000003 is a known prime number.

The code correctly checks divisors up to sqrt(1000003) without overflow and finds no divisor.

❓ Predict Output

advanced

Output of Prime Check for 0

What is the output of this C# code when checking if 0 is prime?

DSA C#

using System;
class Program {
  static bool IsPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
  static void Main() {
    Console.WriteLine(IsPrime(0));
  }
}

A Runtime error

B False

C True

D Compile error

💡 Hint

0 is not a prime number.

The code returns false immediately for n <= 1.

❓ Predict Output

expert

Output of Prime Check for Negative Number -7

What is the output of this C# code when checking if -7 is prime?

DSA C#

using System;
class Program {
  static bool IsPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
  static void Main() {
    Console.WriteLine(IsPrime(-7));
  }
}

A Compile error

B True

C False

D Runtime error

💡 Hint

Negative numbers are not prime.

The code returns false immediately for n <= 1, including negative numbers.

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