Prime Number Program in C

Prime Number program in C
Prime Number Program in C

Problem Statement: Given a number N, Check if the number is Prime or not.

Examples:

Example 1:
Input: N = 7
Output: Prime Number.

Input: N = 8
Output: Not Prime.

DisclaimerDon’t jump directly to the solution, try it out yourself first.

What is a Prime Number?

A natural number is called a prime number if it is divisible only by 1 and itself. Example: 1, 2, 3, 5, 7, …

Can you think of a naive solution now?

Yes, we simply need to check if the given number is divisible by any number between 2 and N – 1, if yes then it is not prime otherwise it is a prime number.

Approach:

  • We will run a loop from 2 to 1 number less than the given number, N.
  • Now we will check if the given number is divisible by any number in that range.
  • If it gets divided by any number then it is not a prime number else it is a prime number.

Code:

C Program

#include <stdio.h>
#include<math.h>
int prime(int n){
    for(int i=2;i<n;i++)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}

int main() {
    int n=7;
    if(prime(n))
        printf("It is a prime number");
    else
        printf("It is not a prime number");
    return 0;
}

Output: It is a prime number

Time Complexity: O(n)

Space Complexity: O(1)

Can we optimise the above approach?

Yes, we can to some extent. Before that let me ask you a few questions:

  • Can 10 be ever divided by a number greater than 5?
  • Can 15 be ever divided by a number greater than 7?
  • Can 18 be ever divided by a number greater than 9?

No, right?

So you can’t divide a number(N) completely by any number greater than (N/2). Therefore, we don’t need to check for every number from 2 to N-1, we just need to check for every number from 2 to (N/2).

C Program

#include <stdio.h>
#include<math.h>
int prime(int n){
    for(int i=2;i<n/2;i++)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}

int main() {
    int n=7;
    if(prime(n))
        printf("It is a prime number");
    else
        printf("It is not a prime number");
    return 0;
}

Output: It is a prime number

Time Complexity: O(n)

Space Complexity: O(1)

Is there any library function to check prime numbers in C?

No, there is no builtin function in C to check for prime.

Special thanks to Subhrajit Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article