C Program to Check Whether a Number Is Prime

C Program for Prime Numbers Using For Loop

Algorithm to Find Prime Number Program in C

STEP 1: Take num as input.

STEP 2: Initialize a variable temp to 0.

STEP 3: Iterate a “for” loop from 2 to num/2.

STEP 4: If num is divisible by loop iterator, then increment temp.

STEP 5: If the temp is equal to 0,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.     

Pseudocode to Find Prime Number Using For Loop

Start

   Input num

   Initialize variable temp = 0 

   FOR loop = 2 to num/2 

      IF num is divisible by loop

         Increment temp

      END IF 

   END FOR      

      IF temp is equal to 0

         RETURN “Num IS PRIME”

      END IF 

      ELSE

         RETURN “Num IS NOT PRIME”

      END ELSE 

End 

Also Read: Use of C Language

Master Core Java 8 Concepts, Java Servlet & More!

Java Certification TrainingENROLL NOW

Implementing C program for prime numbers Using For Loop

#include <stdio.h>

int main()

{

    int i, num, temp = 0; 

    // read input from user.

    printf("Enter any numb to Check for Prime: ");

    scanf("%d", &num);

    // iterate up to n/2.

    for (i = 2; i <= num / 2; i++)

    {

        // check if num is divisible by any number.

        if (num % i == 0)

        {

            temp++;

            break;

        }

    } 

    // check for the value of temp and num. 

    if (temp == 0 && num != 1)

    {

        printf("%d is a Prime number", num);

    }

    else

    {

        printf("%d is not a Prime number", num);

    }

    return 0;

}

In the above program, a “for” loop is iterating from 2 to n/2. Where “n” is the input number. We are checking for every number till n/2 if it divides the num. If any multiple of n is found, update the value of temp and return “Not prime” else “Prime”. 

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

Time Complexity: O(n)

As the loop is iterating from 2 to n/2, the time complexity for the worst case will be O(n), where n is the input element.

Space Complexity: O(1)

The program is not using any extra auxiliary space, only constant space is being used. So, the space complexity is O(1).

Reason for Iterating the Loop Till n/2

You could ask why we are iterating the loop till n/2 instead of n. What’s the reason for leaving the other half? Let us understand this with the help of examples. Consider the factors of the integer 12. The factors are 1, 2, 3, 4, 6, 12. You can observe here that after 12/2 i.e. 6, there is only one factor left that is the number itself (12 in this case). This is true for all integers. 

Now consider a prime integer 17. The factors of 17 are 1. After 17/2, i.e. 8.5 there is only one factor i.e. 17. So, to find if a number is prime or not, finding only one factor is enough. That one factor can be found in the first half, as you can notice that there is only one factor in the second half and i.e. the number itself.

Also Read: C Program for Bubble Sort to Sort Elements in An Order

Get the Coding Skills You Need to Succeed

Full Stack Developer - MERN StackExplore Program

C Program for Prime Numbers Using While Loop

Algorithm to Find Prime Number Program in C

STEP 1: Take num as input.

STEP 2: Initialize a variable temp to 0.

STEP 3: Initialize the iterator variable loop to 2.

STEP 4: Iterate a “while” with the condition, loop <= num/2.

STEP 5: If num is divisible by loop iterator, then increment temp.

STEP 6: If the temp is equal to 0,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.

Pseudocode to Find Prime Number Using While Loop

Start

   Input num

   Initialize variable temp = 0   

   Initialize loop = 2

   WHILE loop <= num/2

      IF num is divisible by loop

         Increment temp

      END IF 

   END WHILE  

      IF temp is equal to 0

         RETURN “Num IS PRIME”

      END IF 

      ELSE

         RETURN “Num IS NOT PRIME”

      END ELSE 

End

Implementing C Program for Prime Numbers Using While Loop

#include <stdio.h>

int main()

{

    int num, temp = 0;

    // read input from the user.

    printf("Enter any number to Check for Prime: ");

    scanf("%d", &num);

    // initialization

    int i = 2; 

    // loop condition

    while (i <= num / 2)

    {

        // check if num is divisible by any number.

        if (num % i == 0)

        {

            temp++;

            break;

        }

        // incrementation

        i++;

    }

    // check for the value of temp and num.

    if (temp == 0 && num != 1)

    {

        printf("%d is a Prime Number", num);

    }

    else

    {

        printf("%d is Not a Prime Number", num);

    }

    return 0;

}

In the following program, we have implemented a “while” loop instead of a “for” loop. The logic is the same as the previous program. 

Become an Automation Test Engineer in 11 Months!

Automation Testing Masters ProgramExplore Program

Time Complexity: O(n)

The loop in the program runs from 2 to n/2, therefore, the time complexity for the worst case will be O(n). Here, n is the input element.

Space Complexity: O(1)

In this program, only constant space is being used for some variables. Therefore, the space complexity is O(1).

Boost Your Coding Skills. Nail Your Next Interview

Full Stack Developer - MERN StackExplore Program

C Program for Prime Numbers Using Functions

Algorithm to Find Prime Number

STEP 1: Define a function that accepts an integer num.

STEP 2: Initialize a variable temp to 0.

STEP 3: Iterate a “for” loop from 2 to num/2.

STEP 4: If num is divisible by loop iterator, then increment temp.

STEP 5: Return num.

STEP 6: In the main function: If the temp is equal to 0,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.

Pseudocode to Find Prime Number Using Functions

Start

   FUNCTION find_Prime (num) 

       Initialize variable temp = 0

        FOR loop = 2 to num/2

           IF num is divisible by loop

              Increment temp

           END IF

        END FOR  

           IF temp is equal to 0

             RETURN “Num IS PRIME”

           END IF

           ELSE

              RETURN “Num IS NOT PRIME”

           END ELSE         

   END FUNCTION

END 

Implementing C Program for Prime Numbers Using Functions

#include <stdio.h> 

// function to check if 

// the num is prime or not.

int find_Prime(int num)

{

    int i, temp = 0; 

    // iterate up to num/2.

    for (i = 2; i <= num / 2; i++)

    {

        // if num has factors, 

        // update temp.

        if (num % i == 0)

        {

            temp++;

        }

    }

    return temp;

} 

int main()

{

    int num, temp = 0; 

    printf("Enter any number to Check for Prime: ");

    scanf("%d", &num);

    // function call

    temp = find_Prime(num);

    if (temp == 0 && num != 1)

    {

        printf("\n %d is a Prime Number", num);

    }

    else

    {

        printf("\n %d is Not a Prime Number", num);

    }

    return 0;

}

Become an Automation Test Engineer in 11 Months!

Automation Testing Masters ProgramExplore Program

Time Complexity: O(n)

The function has only one “for” loop that runs from 2 to n/2. Therefore, in the worst case, the time complexity will be O(n).

Space Complexity: O(1)

No extra space is being used here. The function uses only constant space to store the variables. So, the space complexity will be O(1).

Also Read: Learn C Program for String Palindrome

C Program for Prime Numbers Using Recursion

Algorithm to Find Prime Number

STEP 1: Define a recursive function that accepts an integer num.

STEP 2: Initialize a variable ”i” to 2.

STEP 3: If num is equal to 0 or 1, then RETURN false.

STEP 4: If num is equal to “i”, then RETURN true.

STEP 4: If num is divisible by “i”, then RETURN false.

STEP 5: Increment “i”.

STEP 6: Recursively call the function and pass num as an argument.

Pseudocode to Find Prime Number Using Recursion

Start

   FUNCTION find_Prime (num) 

       Initialize variable i = 2   

       IF num is equal to i

          RETURN true

       END IF 

       IF num is divisible by i

              RETURN false

       END IF  

       Recursively call find_Prime

   END FUNCTION

END 

Implementing C program for Prime Numbers Using Recursion

#include <stdio.h>

#include <stdbool.h> 

// recursive function to check if a number

// is prime or not.

bool find_Prime(int num)

{

    static int i = 2; 

    // Base Case

    if (num == 0 || num == 1)

    {

        return false;

    } 

    // Recursive Case

    if (num == i)

        return true; 

    // check if num is divisible by any number

    if (num % i == 0)

    {

        return false;

    }

    i++; 

    // recursive function call.

    return find_Prime(num);

} 

int main()

{

    // test case 1

    int num = 20;

    if (find_Prime(num))

    {

        printf("%d is a Prime number\n", num);

    }

    else

    {

        printf("%d is not a Prime number \n", num);

    }

    // test case 2

    num = 2;

    if (find_Prime(num))

    {

        printf("%d is a Prime number\n", num);

    }

    else

    {

        printf("%d is not a Prime number \n", num);

    }

    return 0;

}

This is a recursive approach to find the prime numbers. Here, a recursive function find_Prime is made that simply checks if the num is divisible by any number. If it is, then it returns false else the recursive call is made. This process repeats until any multiple of num is found.

Time Complexity: O(n)

The function is calling itself recursively n times until either a factor is found or one of the conditions is satisfied. Therefore, the time complexity is O(n).

Space Complexity: O(n)

The n calls made by the recursive function will be stored in the stack which will consume space in the memory. Therefore, the space complexity of the recursive approach will be O(n).

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

C Program for Prime Numbers: Optimized Method

Algorithm to Find Prime Number

STEP 1: Take num as input.

STEP 2: Initialize a variable temp to 1.

STEP 3: Iterate a “for” loop from 2 to sqrt(num).

STEP 4: If num is divisible by loop iterator, then update temp value to 0.

STEP 5: If the temp is equal to 1,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.

Pseudocode to Find Prime Number

Start 

   Input num

   Initialize variable temp = 1  

   FOR loop = 2 to sqrt(n) 

      IF num is divisible by loop

         update temp = 0

      END IF

   END FOR      

      IF temp is equal to 1

         RETURN “Num IS PRIME”

      END IF 

      ELSE

         RETURN “Num IS NOT PRIME”

      END ELSE

End 

Implementing C Program for Prime Numbers: Optimized Method 

#include <stdio.h>

#include <math.h>

int main()

{

    int num, i, temp = 1; 

    // read the input from the user.

    printf("Enter a number: ");

    scanf("%d", &num); 

    // initialize i as 2.

    // iterate upto sqrt of num.

    for (i = 2; i <= sqrt(num); i++)

    {

        // check if num is divisible by any number.

        if (num % i == 0)

        {

            // update temp.

            temp = 0;

            break;

        }

    } 

    // 1 is divisible by every

    // number and is not prime.

    if (num <= 1)

        temp = 0; 

    if (temp == 1)

    {

        printf("%d is a Prime Number", num);

    }

    else

    {

        printf("%d is not a Prime Number", num);

    } 

    return 0;

}

In the above program, we have used an optimized solution to check if a number is prime or not. Here, instead of iterating the loop up to the number itself, we are iterating it up to its square root  (√n). This is because the smallest factor of a number (greater than 1) can not be greater than the square root of the number. For example, for 64 the smallest factor is 2 which is not greater than √64.

Time Complexity: O(n1/2)

This is because the “for” loop is iterating from 2 to the square root of (√n), where n is the input element.

Space Complexity: O(1) 

No extra space is being used in the program. Only a constant auxiliary space is used to store variables and iteration is done in place.

Unleash a High-paying Automation Testing Job!

Automation Testing Masters ProgramExplore Program

C Program for Prime Numbers Within a Range

Algorithm to Find Prime Number

STEP 1: Take the range values left and right as input.

STEP 2: Initialize a loop iterator num to left.

STEP 3: Iterate a “for” loop from left to right.

STEP 4: Iterate a “for” loop from 2 to num/2.

STEP 5: Initialize a variable temp to 0.

STEP 6: If num is divisible by loop iterator, then increment temp.

STEP 5: If the temp is equal to 0,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.

Pseudocode to Find Prime Number Within a Range

Start

   Input left, right  

   FOR num = left to right

      FOR loop = 2 to num/2 

         Initialize variable temp = 0        

         IF num is divisible by loop

            Increment temp

         END IF  

      END FOR

                 IF temp is equal to 0

           RETURN “Num IS PRIME”

         END IF 

         ELSE

           RETURN “Num IS NOT PRIME”

         END ELSE 

End

Implementing C Program for Prime Numbers Within a Range

#include <stdio.h>

int main()

{

    int i, num, temp, sum = 0, left, right;

    // read the values of the range form the user.

    printf("Enter the left & right Values: ");

    scanf("%d %d", &left, &right); 

    // iterate “for” loop within the given range.

    for (num = left; num <= right; num++)

    {

        temp = 0;

        // for loop to check for the prime numbers.

        for (i = 2; i <= num / 2; i++)

        {

            // check if num is divisible by any number.

            if (num % i == 0)

            {

                temp++;

                break;

            }

        }

        // check for the values of temp and num.

        if (temp == 0 && num != 1)

        {

            sum = sum + num;

        }

    }

    printf("Sum of Prime nums between %d and %d =  %d", left, right, sum);

    return 0;

}

In the above program, we are printing the sum of the prime numbers in the given range. The starting and ending points are being read by the user. We have iterated a nested for loop. The outer loop is running from the left till right and the inner loop is running up to n/2 for each iteration of the outer loop.

Time Complexity: O((right-left)*num)

(Here, “num” is the input number, “left” and “right” are the starting and ending point of the given range). We have used a nested “for” loop where the outer loop is iterating from “left” to “right”, the inner loop is iterating from 2 up to n/2. So, the outer loop runs (right-left) times, and the inner loop iterates “num” times, 

Space Complexity: O(1)

No extra space is being used here. The function uses only constant space to store the variables. So, the space complexity will be O(1).

C Program for Prime Numbers Using Sieve of Eratosthenes

Algorithm to Find Prime Number

STEP 1: Take a natural number num as an input.

STEP 2: Create a boolean array isPrime[] and initialize all its elements to 1 (assuming initially all elements are prime).

STEP 3: If an element k is equal to 1 (or true), mark all its multiples greater than k2 to 0.

STEP 4: Repeat STEP 2 for all unmarked (equal to 1 or true) elements until the square root of the num is reached.

STEP 5: Iterate over the boolean array isPrime[], If the isPrime[i] is equal to 1,

    Return “Num IS PRIME”.

Else,

    Return “Num IS NOT PRIME”.

Pseudocode to Find Prime Number Using Sieve of Eratosthenes

Start

   Input num

   Create a boolean array isPrime[]

   Initialize all elements of isPrime[] to 1   

   FOR k = 2 to k2 <= num 

      IF isPrime[k] is equal to 1 

         FOR i = k2 to i <= num

            isPrime[i] = 0

         END FOR

      END IF        

   END FOR   

   FOR loop = 2 to num

      IF isPrime[loop] is equal to 1

         PRINT "isPrime[loop] IS PRIME"

      END IF

   END FOR 

End

Implementing C Program for Prime Numbers Using Sieve of Eratosthenes

#include <stdio.h>

#include <stdbool.h>

#include <string.h> 

// function to find all the

// prime numbers from 1 to num.

void find_Prime(int num)

{    

    // initialize all elements of 

    // the array isPrime as true i.e., 1.

    // An element of the array will 

    // be updated to false, if it is not prime.

    bool isPrime[num + 1];

    memset(isPrime, true, sizeof(isPrime));

    for (int k = 2; k * k <= num; k++)

    {

        // if isPrime[k] is not updated,

        // then it is a Prime.

        if (isPrime[k] == true)

        {

            // update all the multiples of 

            // k as false, starting from 

            // its square upto num

            for (int i = k * k; i <= num; i += k)

                isPrime[i] = false;

        }

    } 

    // print the Prime numbers.

    for (int k = 2; k <= num; k++)

        if (isPrime[k])

            printf("%d, ", k);

} 

int main()

{

    int num = 30;

    printf("Following are the Prime numbers smaller ");

    printf("%d, than or equal to ", num);

    printf("\n");

     // function call

    find_Prime(num);

    return 0;

}

The above approach is based upon the sieve of Eratosthenes. We have defined an array of the boolean type whose all elements are initially true. True means we have supposed that initially, all the elements are prime. If a number is updated as false, then it will not be a prime number. We have iterated a loop starting from 2 that will mark all the multiples of 2 which are greater than or equal to its square up to num as false. We will repeat this process up to √num. After this, the elements that remain unmarked (or true) will all be the prime numbers.

Time Complexity: O(n*log(log(n))) 

The time complexity of marking all non-prime numbers is assumed to be constant. Now to find the time complexity to run the loop until k, the equation becomes,

By solving this equation using formulae of Harmonic Progression and Taylor series expansion, Euler’s Formula followed by summation and simplification, the final result can be deduced which is equal to n * log(log(n)).

Space Complexity: O(n)

Space is consumed by the boolean array isPrime which is declared to be of a size equal to num. Therefore, the time complexity is O(n), where n is the input element.

That was all about C program for Prime numbers.

Accelerate your career as a skilled MERN Stack Developer by enrolling in a unique Full Stack Developer - MERN Stack Master's program. Get complete development and testing knowledge on the latest technologies by opting for the MERN Stack Developer Course. Contact us TODAY!

Final Thoughts!

To wrap up, in this article, you have learned about the multiple ways to write a C program for prime numbers. You started with a quick introduction to prime numbers as well as some interesting facts about prime numbers. 

While exploring the realm of programming, delving into algorithmic challenges such as creating a C program to check whether a number is prime can be both intriguing and enlightening. However, if you're aiming to broaden your horizons and master a suite of technologies that will prepare you for a versatile career in software development, considering a java full stack developer course might be your next strategic move.

Moving ahead, in the C program for Prime numbers article you saw different techniques to check for a prime number using for loops, while loops, functions, recursion, optimized method, etc. You learned how to print prime numbers within a range and one of the most popular methods called Sieves of Erastosthenes. You saw the algorithm, pseudocode, C program, time, and space complexities for each of the methods that we have discussed.

If you want to build a career inFull Stack Developer - MERN Stack, you should definitely check out our 9-month instructor-led certification training on Full Stack Web Development. The course is strategically designed by industry experts to teach you all the trending technologies that are essential in the world of Software Development. This includes Agile methodologies, DevOps culture, Java and it’s frameworks such as Hibernate, JPA, Spring, Spring Boot, etc., JS, CSS, HTML, etc.

If you have a knack for learning new technologies, then you should certainly check out our complete list of free online courses. If you have any queries in this “C Program for Prime Numbers” article or suggestions for us, please mention them in the comment box and our experts answer them for you as soon as possible.

Happy Learning!