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.