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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prime Check Function for 29

What is the output of the following C++ code when checking if 29 is prime?

DSA C++

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= std::sqrt(n); ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 29;
    if (isPrime(num))
        std::cout << "29 is prime" << std::endl;
    else
        std::cout << "29 is not prime" << std::endl;
    return 0;
}

A 29 is prime

B Runtime error

C Compilation error

D 29 is not prime

💡 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 loop checks divisors up to sqrt(29) which is about 5.3, and finds none.

❓ Predict Output

intermediate

Output for Number 1 in Prime Check

What will the output be when checking if 1 is prime using the same function?

DSA C++

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= std::sqrt(n); ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 1;
    if (isPrime(num))
        std::cout << "1 is prime" << std::endl;
    else
        std::cout << "1 is not prime" << std::endl;
    return 0;
}

A Runtime error

B 1 is prime

C Compilation error

D 1 is not prime

💡 Hint

Remember prime numbers are greater than 1.

The function returns false for 1 because it is not greater than 1, so output is '1 is not prime'.

🔧 Debug

advanced

Identify the Error in Prime Check Loop

What error will this code produce when checking if 25 is prime?

DSA C++

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < std::sqrt(n); ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 25;
    if (isPrime(num))
        std::cout << "25 is prime" << std::endl;
    else
        std::cout << "25 is not prime" << std::endl;
    return 0;
}

A 25 is not prime

B 25 is prime

C Compilation error

D Runtime error

💡 Hint

Check the loop condition carefully.

The loop uses i < sqrt(n) instead of i <= sqrt(n), so it misses checking divisor 5 for 25. Thus, it incorrectly returns true.

❓ Predict Output

advanced

Output of Prime Check for Large Number 97

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

DSA C++

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= std::sqrt(n); ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num = 97;
    if (isPrime(num))
        std::cout << "97 is prime" << std::endl;
    else
        std::cout << "97 is not prime" << std::endl;
    return 0;
}

A Compilation error

B 97 is not prime

C 97 is prime

D Runtime error

💡 Hint

Check divisors up to sqrt(97) which is about 9.8.

97 is prime because no divisor from 2 to 9 divides it evenly.

🧠 Conceptual

expert

Why Check Divisors Only up to Square Root?

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

A Because any factor larger than the square root would have a corresponding factor smaller than the square root, so checking beyond is redundant.

B Because checking beyond the square root causes runtime errors.

C Because the square root is the largest possible divisor of any number.

D Because numbers larger than the square root are always prime.

💡 Hint

Think about pairs of factors.

If n = a * b and both a and b were greater than sqrt(n), then a * b would be greater than n, which is impossible. So one factor must be less than or equal to sqrt(n).

Practice

1. What does it mean if a number is prime?

easy

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

B. It is divisible by 2 only.

C. It is an even number greater than 2.

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 that a prime number has exactly two distinct positive divisors: 1 and itself.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime means divisible only by 1 and itself [OK]

Common Mistakes:

• Thinking all even numbers are prime
• Confusing prime with odd numbers
• Assuming 1 is prime

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

easy

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

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

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

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

Solution

1. Step 1: Analyze loop range for prime check

   We check divisors from 2 up to but not including n to find any divisor.

2. Step 2: Check correctness of each option

   for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; correctly checks divisors from 2 to n-1 and returns false if divisible, else true. for (int i = 2; i <= n; i++) { if (n % i == 0) return false; } return true; incorrectly includes n itself, causing false negatives. for (int i = 1; i < n; i++) { if (n % i == 0) return false; } return true; starts from 1, which divides all numbers. for (int i = 2; i < n/2; i++) { if (n % i == 0) return true; } return false; returns true on first divisor found, which is incorrect logic.

3. Final Answer:

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

4. Quick Check:

   Loop from 2 to n-1 and check divisibility [OK]

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

Common Mistakes:

• Checking divisibility by 1 or n itself
• Looping beyond n
• Returning true too early

3. What is the output of the following C++ code?

int n = 11;
bool isPrime = true;
for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) {
        isPrime = false;
        break;
    }
}
std::cout << (isPrime ? "Prime" : "Not Prime") << std::endl;

medium

A. Runtime Error

B. Not Prime

C. Compilation Error

D. Prime

Solution

1. Step 1: Understand the loop and condition

   The loop checks divisors from 2 to n/2 (which is 5 for n=11). It tests if 11 is divisible by any number in this range.

2. Step 2: Check divisibility for each i

   11 % 2 != 0, 11 % 3 != 0, 11 % 4 != 0, 11 % 5 != 0. No divisor found, so isPrime remains true.

3. Final Answer:

   Prime -> Option D

4. Quick Check:

   11 has no divisors except 1 and itself [OK]

Hint: Check divisors only up to n/2 for efficiency [OK]

Common Mistakes:

• Looping up to n instead of n/2
• Not breaking loop on divisor found
• Misinterpreting output

4. Find the error in this C++ code that checks if n is prime:

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

medium

A. Loop should start from 1, not 2.

B. Returns true when a divisor is found, should return false instead.

C. Function should return true for n <= 1.

D. No error, code is correct.

Solution

1. Step 1: Analyze return values on divisor found

   The code returns true immediately when a divisor is found, which means it claims the number is prime incorrectly.

2. Step 2: Correct logic for prime check

   When a divisor is found, the function should return false (not prime). If no divisor is found, return true.

3. Final Answer:

   Returns true when a divisor is found, should return false instead. -> Option B

4. Quick Check:

   Return false on divisor found [OK]

Hint: Return false when divisor found, true otherwise [OK]

Common Mistakes:

• Returning true on divisor found
• Loop starting at 1
• Not handling n <= 1 correctly

5. You want to optimize prime checking for large numbers by checking divisors only up to the square root of n. Which code snippet correctly implements this?

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

hard

A. Incorrect: returns true inside the loop when divisor found.

B. Incorrect: loop should go up to n/2, not sqrt(n).

C. Correct: checks divisors up to sqrt(n) and returns false if divisible.

D. Incorrect: should start loop from 1 instead of 2.

Solution

1. Step 1: Understand optimization using square root

   Any divisor larger than sqrt(n) pairs with a smaller divisor, so checking up to sqrt(n) is enough.

2. Step 2: Verify code logic

   The loop runs from 2 to sqrt(n), returns false if divisor found, else true after loop ends. This is correct and efficient.

3. Final Answer:

   Correct: checks divisors up to sqrt(n) and returns false if divisible. -> Option C

4. Quick Check:

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

Hint: Check divisors only up to sqrt(n) for speed [OK]

Common Mistakes:

• Looping up to n/2 instead of sqrt(n)
• Starting loop at 1
• Returning true inside loop on divisor found