C Program to Check if a number is prime or not.

In this article, we are going to learn how to check whether a number is prime or not using C programming. Before we write code for this problem, we first need to understand prime numbers.

What is a Prime Number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In simpler terms, a prime number is a number that cannot be divided evenly by any other number except for 1 and itself.

For example, 2, 3, 5, 7, 11, 13, 17, and 19 are all prime numbers.

There are multiples way to check whether a number is prime or not and here we are going to learn a few of those methods and also write C code for their implementation.

Approach 1: Basic Trial Division Method.

In this approach, we will check if the given number is divisible by any integer from 2 to the square root of the number. If we find any divisor, the number is not prime; otherwise, it is prime.

Step-by-step algorithm:

Step 1: Get the integer input that you want to check for prime.

Step 2: Check the two base cases, if the input value is less than or equal to 1 then it is not a prime number.

Step 3: Calculate the square root of the input number and round it to the nearest integer. Let's call this value "sqrt_num."

Step 4: Start a loop from 2 to "sqrt_num" (inclusive). For each integer "i" in the loop:

Check if the input number is divisible by "i" (i.e., input number % i == 0).
If it is divisible, the input number is not a prime number. Return "Not Prime."

Step 5: If the loop completes without finding any divisors (i.e., the input number is not divisible by any number from 2 to "sqrt_num"), then the input number is a prime number. Return "Prime."

C Code Implementation:

//C Program to check prime number
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime_basic(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return false; 
    }

    int sqrt_num = (int)sqrt(num);
    for (int i = 2; i <= sqrt_num; i++) {
        // Found a divisor, not a prime number
        if (num % i == 0) {
            return false; 
        }
    }
    // No divisors found, the number is prime
    return true; 
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_basic(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 5
5 is a prime number.

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

Approach 2: Optimized Trial Division Method.

In this approach, we can make some optimizations to the basic trial division method. We will check if the number is divisible by 2 or 3, and then check for divisors starting from 5, skipping multiples of 2 and 3.

Step-by-step algorithm:

Step 1: Get the integer number that you want to check for primality.

Step 2: Check the base cases:

If the input number is less than or equal to 1, it is not a prime number.
If the input number is 2 or 3, it is a prime number. Return "Prime."

Step 3: If the input number is divisible by 2 or 3, it is not a prime number. Return "Not Prime."

Step 4: Calculate the square root of the input number and round it to the nearest integer. Let's call this value "sqrt_num."

Step 5: The code starts a loop from 5 to "sqrt_num" (inclusive) with a step size of 6. This is an optimization to check only certain potential divisors, which are 5 and 7 (since 5 + 2 = 7).

For each value of "i" in the loop, it checks if the input number is divisible by "i" or "i + 2" using the modulo operator (%).
If the input number is divisible by "i" or "i + 2," it means the number is not a prime, and the function returns "false."

Step 6: If the loop completes without finding any divisors (i.e., the input number is not divisible by any number in the optimized set of potential divisors), then the input number is a prime number.

C Code Implementation:

//C Program to check if a number is prime or not
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime_optimized(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return false; 
    }
    // 2 and 3 are prime numbers
    if (num <= 3) {
        return true; 
    }
    // Numbers divisible by 2 or 3 are not prime
    if (num % 2 == 0 || num % 3 == 0) {
        return false; 
    }

    int sqrt_num = (int)sqrt(num);
    for (int i = 5; i <= sqrt_num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false; // Found a divisor, not a prime number
        }
    }
    // No divisors found, the number is prime
    return true; 
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_optimized(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 17
17 is a prime number.

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

Approach 3: Check Prime Number using Wilson’s Theorem.

Wilson's Theorem is a mathematical theorem that provides a condition for a positive integer "p" to be prime. According to Wilson's Theorem, "p" is a prime number if and only if (p - 1)! ≡ -1 (mod p), where "!" represents the factorial operation and "≡" denotes congruence.

Step-by-step algorithm:

Step 1: Input a positive integer "num" that you want to check for primality.

Step 2: If the value of "num" is less than or equal to 1, it is not a prime number. Return false.

Step 3: If "num" is 2 or 3, it is a prime number. Return true.

Step 4: Check if "num" is divisible by 2 or 3. If it is, it is not a prime number. Return false.

Step 5: Calculate the factorial of "num - 1" using a loop and the factorial function.

The factorial function multiplies all integers from 2 to "num - 1" to calculate the factorial value.

Step 6: Check if (num - 1)! + 1 is divisible by "num" using the modulo operator.

If (num - 1)! + 1 is congruent to 0 modulo "num," then "num" satisfies Wilson's Theorem, and it is a prime number. Return true.

Step 7: If (num - 1)! + 1 is not divisible by "num," "num" does not satisfy Wilson's Theorem, and it is not a prime number. Return false.

C Code Implementation of Wilson's Theorem,

//C Program to check prime number using Wilson’s Theorem
#include <stdio.h>

// Function to calculate the factorial of a number
int factorial(int num) {
    // Factorial of 0 and 1 is 1
    if (num == 0 || num == 1) {
        return 1; 
    }

    int result = 1;
    // Calculate the factorial
    for (int i = 2; i <= num; i++) {
        result *= i; 
    }

    return result;
}

// Function to check if a number is prime using Wilson's Theorem
int is_prime_wilson(int num) {
    // Numbers less than or equal to 1 are not prime
    if (num <= 1) {
        return 0; 
    }

    // Check if (num - 1)! ≡ -1 (mod num)
    if ((factorial(num - 1) + 1) % num == 0) {
        return 1; // The number satisfies Wilson's Theorem, it is prime
    } else {
        return 0; // The number does not satisfy Wilson's Theorem, it is not prime
    }
}

int main() {
    int number;
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    if (is_prime_wilson(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Output:

Enter a positive integer: 7
7 is a prime number.

Time Complexity: O(n)

Space Complexity: O(1)

Note: Wilson's Theorem is not practical for large numbers as the factorial operation becomes computationally expensive.(alert-passed)

C Program to Check if a number is prime or not.

What is a Prime Number?

Approach 1: Basic Trial Division Method.

Approach 2: Optimized Trial Division Method.

Approach 3: Check Prime Number using Wilson’s Theorem.

No comments:

Post a Comment