C Program for Prime Number

A natural number is said to be prime if it is only divisible by itself and 1. In short, a prime number has only two factors that are 1 and the number itself. The numbers that are not prime are called composite numbers. 

A prime number can be written as a product of only two numbers. For example, consider 3. Now, 3 can be written in the form of the product of two numbers in only one way i.e., 1 * 3. Whereas, 8 which is a composite number can be written as 1 * 8 and 2 * 4. 

The following diagrammatic illustration shows the prime numbers between 1 and 100. Observe this table to find some interesting facts about the prime numbers which are discussed in the next section.

C_Program_for_Prime_Number_1

Interesting Facts About Prime numbers

  • There is only a single even prime number i.e. 2. 
  • There is only one pair of consecutive prime numbers i.e. (2,3).
  • You can express all prime numbers in the form of 6k+1 or 6k-1 (where k is a natural number). 2 and 3 are the only exceptions that do not lie in this case.
  • All even natural numbers can be represented as the sum of two prime numbers. 2 is the exceptional case here.
  • Lemoine’s Conjecture: According to this theorem, an odd integer n (where n > 5) can be represented in the form: (odd prime + even semiprime). A number is said to be a semiprime if it can be represented as a product of two prime numbers.
  • Fermat’s Little Theorem: According to this theorem, for any prime number n, there lies a number p in the range [1, n) such that,

pn-1 ≡ 1 (mod n)

OR 

pn-1 % n = 1

  • Prime Number Theorem: According to this theorem, the probability of a randomly selected number n to be a prime is inversely proportional to the log(n) or the digits in the number n.

  • Wilson’s Theorem: According to this theorem, a natural number n (where n >1) is said to be a prime number if and only if the following conditions hold true.

(n - 1) ! ≡  -1   mod n 

OR  

(n - 1) ! ≡  (n-1) mod n

C Program for Prime Numbers Using For Loop

Algorithm to Find Prime Number

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

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 

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Implementing C program for prime numbers

#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;

}

C_Program_for_Prime_Number_2

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”. 

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.  

C Program for Prime Numbers Using While Loop

Algorithm to Find Prime Number

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

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

#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;

}

C_Program_for_Prime_Number_3.

In the following program, we have implemented a “while” loop instead of a “for” loop. The logic is the same as the previous 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).

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

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

#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;

}

C_Program_for_Prime_Number_4.

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).

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

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

#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;

}

C_Program_for_Prime_Number_5.

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).

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

#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;

}

C_Program_for_Prime_Number_6  

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.

Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE CoursesEnroll Now
Stand Out From Your Peers this Appraisal Season

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

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

#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;

}

C_Program_for_Prime_Number_7. 

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

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

#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;

}

C_Program_for_Prime_Number_8 

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.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

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. 

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 in Full Stack Web Development, 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!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.