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 this C code when checking if 29 is prime?

DSA C

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int num = 29;
    if (isPrime(num))
        printf("%d is prime\n", num);
    else
        printf("%d is not prime\n", num);
    return 0;
}

A Compilation error

B 29 is not prime

C 29 is prime

D Runtime error

💡 Hint

Check divisors from 2 up to square root of the number.

29 is a prime number because it has no divisors other than 1 and itself. The code checks divisors up to sqrt(29) and finds none.

❓ 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

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int num = 1;
    if (isPrime(num))
        printf("%d is prime\n", num);
    else
        printf("%d is not prime\n", num);
    return 0;
}

A 1 is not prime

B 1 is prime

C Compilation error

D Runtime error

💡 Hint

Remember prime numbers are greater than 1.

1 is not considered a prime number. The code returns false for numbers less than or equal to 1.

🔧 Debug

advanced

Find the bug in prime check function

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

DSA C

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int num = 4;
    if (isPrime(num))
        printf("%d is prime\n", num);
    else
        printf("%d is not prime\n", num);
    return 0;
}

A 4 is prime

B Compilation error

C Infinite loop

D 4 is not prime

💡 Hint

For n=4, n/2=2. Does the loop check i=2?

For n=4, n/2 = 2 (integer division). The loop condition i < 2 means the loop doesn't execute (i starts at 2, 2 < 2 is false). Thus, it doesn't check if 2 divides 4 and incorrectly returns true. Output: "4 is prime". The bug is in the loop upper bound; it should be i <= n/2 or better, i * i <= n.

❓ Predict Output

advanced

Output for prime check of 49

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

DSA C

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int num = 49;
    if (isPrime(num))
        printf("%d is prime\n", num);
    else
        printf("%d is not prime\n", num);
    return 0;
}

A Runtime error

B 49 is prime

C Compilation error

D 49 is not prime

💡 Hint

49 is 7 times 7.

49 is not prime because it is divisible by 7. The code checks divisors up to sqrt(49) = 7 and finds 7 divides 49.

🧠 Conceptual

expert

Why check divisors only up to square root?

Why does the prime check function only test divisors up to the square root of the number?

A Because numbers larger than the square root are always prime

B Because any factor larger than the square root would have a matching smaller factor already checked

C Because checking beyond the square root causes runtime errors

D Because the square root is the largest possible divisor

💡 Hint

Think about pairs of factors.

If a number n has a factor larger than sqrt(n), it must be paired with a factor smaller than sqrt(n). So checking up to sqrt(n) is enough to find any divisor.

Practice

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

easy

A. It is divisible by 2.

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

C. It is an even number.

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

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states this definition. Options B, C, and D are incorrect because they describe properties that do not define prime numbers.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime numbers have only 1 and itself as divisors [OK]

Common Mistakes:

• Thinking all even numbers are prime
• Confusing prime with composite numbers
• Including 1 as a prime number

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

easy

A. for(int i = 1; i < n; i++) { if(n % i == 0) return 0; } return 1;

B. for(int i = 2; i <= n; i++) { if(n % i == 0) return 0; } return 1;

C. for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1;

D. for(int i = 2; i < n/2; i++) { if(n % i == 0) return 1; } return 0;

Solution

1. Step 1: Analyze loop range for divisor checking

   To check if n is prime, we test divisors from 2 up to n-1. for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; uses i < n, which is correct.

2. Step 2: Check return values and conditions

   for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; returns 0 if a divisor is found, else returns 1 meaning prime. Other options have incorrect loop ranges or return values.

3. Final Answer:

   for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; -> Option C

4. Quick Check:

   Loop from 2 to n-1 and return 0 if divisible [OK]

Hint: Check divisors from 2 to n-1 for prime [OK]

Common Mistakes:

• Checking divisibility by 1
• Looping up to n instead of n-1
• Returning wrong values on divisor found

3. What is the output of the following C code when n = 11?

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

printf("%d", isPrime(n));

medium

A. 1

B. Compilation error

C. 0

D. Infinite loop

Solution

1. Step 1: Analyze the for loop condition

   In C, relational operators (<, <=) associate left-to-right with same precedence. i < i * i <= n parses as (i < (i * i)) <= n. For i ≥ 2, i < i*i is true (1), so 1 <= n is true. Condition always true.

2. Step 2: Runtime behavior

   Loop never terminates (infinite loop). No printf output.

3. Final Answer:

   Infinite loop -> Option D

4. Quick Check:

   (i < i*i) <= n always true [OK]

Hint: C relational ops left-to-right: (i < i*i) <= n always true [OK]

Common Mistakes:

• Thinking chained comparisons cause compile error
• Assuming Python-like chained comparison
• Believing loop stops at sqrt(n)

4. Find the error in this C function to check if n is prime:

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

medium

A. Using assignment operator '=' instead of comparison '==' in if condition

B. Loop should run till i < n, not n / 2

C. Missing return statement at the end

D. No error, code is correct

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses n % i = 0 which is assignment, not comparison.

2. Step 2: Understand impact of assignment in condition

   This causes a syntax error or unintended behavior. It should be n % i == 0 to compare.

3. Final Answer:

   Using assignment operator '=' instead of comparison '==' in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, '=' assigns value [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Looping till n/2 is actually correct optimization
• Ignoring compiler error messages

5. You want to optimize prime checking for large n. Which change improves efficiency the most?

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

hard

A. Change loop to run till i * i <= n instead of i <= n / 2

B. Check divisibility only by even numbers

C. Start loop from 1 instead of 2

D. Remove the initial check for n <= 1

Solution

1. Step 1: Understand loop optimization for prime checking

   Checking divisors up to n/2 is inefficient. We only need to check up to the square root of n.

2. Step 2: Apply loop condition using i * i <= n

   Changing the loop to run while i * i <= n reduces iterations and improves efficiency.

3. Final Answer:

   Change loop to run till i * i <= n instead of i <= n / 2 -> Option A

4. Quick Check:

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

Hint: Check divisors only up to square root of n [OK]

Common Mistakes:

• Checking even numbers only misses odd divisors
• Starting loop from 1 wastes time
• Removing base case causes wrong results