Function Prime or Not – CTS PATTERN

Determine if a given integer is a prime number by fixing the provided implementation.

Understand the Problem

Problem Statement

Function Prime or Not – CTS PATTERN: You are required to fix all logical errors in the given code. You can click on run anytime to check the compilation/execution status of the program. You can use printf to debug your code. The submitted code should be logically/syntactically correct and pass all test cases. Do not write the main() function as it is not required.

Code Approach: For this question, you will need to correct the given implementation. We do not expect you to modify the approach or incorporate any additional library methods.

The function isPrime(int N) accepts an integer N as the input. The function returns 1 if N is a prime number. The function returns 0 if N is not a prime number.

The function compiles fine but fails to return the desired results for some test cases.

Your task is to fix the program so that it passes all test cases.

Constraints

1 ≤ N ≤ 10^6
N is a positive integer
Time complexity should be O(√N)
Space complexity should be O(1)

Examples

Example 1

Input

Output

Explanation

5 is only divisible by 1 and itself, so it's a prime number.

Example 2

Input

Output

Explanation

4 is divisible by 2 (4 = 2 × 2), so it's not a prime number.

Example 3

Input

Output

Explanation

17 is only divisible by 1 and 17, so it's a prime number.

Example 4

Input

Output

Explanation

By definition, 1 is not considered a prime number.

Solution

#include <math.h>

int isPrime(int N) {
    if (N <= 1) {
        return 0;
    }
    
    int sqrtN = (int)sqrt(N);
    for (int divisor = 2; divisor <= sqrtN; divisor++) {
        if (N % divisor == 0) {
            return 0;
        }
    }
    
    return 1;
}

Time:O(√N)

Space:O(1)

Approach:

The C solution:

Includes math.h for the sqrt() function
Handles edge case where N ≤ 1 (returns 0)
Calculates integer square root of N
Iterates from 2 to √N checking for divisors
Returns 0 if any divisor found, 1 if no divisors found

Visual Explanation

Loading diagram...

All Problems