C program for prime numbers: true or false

Interesting facts about prime numbers

• There is only one even prime, ie. 2.
• There is only one pair of consecutive prime numbers, ie. (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 are not in this case.
• All even natural numbers can be represented as a sum of two prime numbers. 2 is the special case here.
• Lemoine’s assumption: According to this theorem, an odd integer n (where n> 5) can be represented in the form: (odd simple + even semisimple). A number is called semisimple if it can be represented as the product of two prime numbers.
• Fermat’s Little Theorem: According to this theorem, for every prime number n there is 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 

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;

}

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

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now

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;

}

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

Full Stack Web Developer Course

To become an expert in MEAN StackView Course

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;

}

FREE Java Certification Training

Learn A-Z of Java like never beforeEnroll Now

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 numbern”, 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 numbern”, 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).

Full Stack Java Developer Course

In Partnership with HIRIST and HackerEarthEXPLORE COURSE

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;

}

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.

Free Course: Programming Fundamentals

Learn the Basics of ProgrammingEnroll Now

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;

}

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 that initially all elements are simple).

STEP 3: If 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 number is reached.

STEP 5: Iterize the boolean array isPrime[]If it’s Prime[i] is equal to 1,

Return “Num IS PRIME”.

otherwise

Return “Num IS NOT PRIME”.

Pseudocode for finding a prime number

Get started

Enter a number

Create a boolean array isPrime[]

Initialize all isPrime elements[] to 1

FOR k = 2 to k2 <= no

IF is Prime[k] is equal to 1

FOR i = k2 to i <= no

is Prime[i] = 0

END FOR

END, IF

END FOR

FOR cycle = 2 to no

IF is Prime[loop] is equal to 1

PRINT „isPrime[loop] E PRIME “

END, IF

END FOR

The end

Implement a C program for prime numbers

#include

#include

#include

// function to find all

// prime numbers from 1 to no.

void find_Prime (int num)

{

// initialize all elements of

// the array is Prime as true, i.e. 1.

// An array element will

// is updated to false if not simple.

bool is Prime[num + 1];

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

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

{

// if it is Prime[k] not updated,

// then this is Prime.

if (is Prime[k] == true)

{

// update all multiples of

// k as false, starting with

// its square to number

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

is Prime[i] = false;

}

}

// print prime numbers.

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

if (is Prime[k])

printf (“% d,”, k);

}

int main ()

{

int number = 30;

printf (“Major numbers follow”);

printf (“% d than or equal to”, number);

printf (” n”);

// call function

find_Prime (number);

return to 0;

}

The above approach is based on the sieve of Eratosthenes. We have defined an array of Boolean type, all elements of which are initially true. True means that we initially assumed that all the elements were simple. If the number is updated as false, it will not be a prime number. We repeated a loop starting at 2, which will mark all multiples of 2 that are greater than or equal to its square to num as false. We will repeat this process until √num. Then the elements that remain unmarked (or true) will all be prime numbers.

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

It is assumed that the time complexity of marking all prime numbers is constant. Now, to find the time complexity to run the cycle to k, the equation becomes,

By solving this equation with the help of formulas for harmonic progression and extension in the Taylor series, Euler’s formula, followed by summation and simplification, the final result can be derived, which is equal to n * log (log (n)).

Complexity of space: O (n)

The space is consumed by the Boolean array isPrime, which is declared for a size equal to num. Therefore the time complexity is O (n), where n is the input element.

This was all about the C program for prime numbers.

Accelerate your career as a qualified MEAN Stack Developer by enrolling in the unique Full Stack Web Developer – the MEAN Stack Master program. Gain full knowledge of developing and testing the latest technologies by choosing the MEAN Stack developer course. Contact us TODAY!

Last thoughts!

To conclude, in this article you learned about the many ways to write a C program for prime numbers. You started with a brief introduction to prime numbers, as well as some interesting facts about prime numbers.

Going forward, in the article on the C program for prime numbers you saw different techniques for checking 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 Erastosthenes Sieves. You saw the complexity of the algorithm, the pseudocode, the C program, the time and space for each of the methods we discussed.

If you want to build a career in Full Stack Web Development, you should definitely check out our 9-month certification training led by Full Stack Web Development instructors. The course is strategically developed by industry experts to teach you all the current technologies that are essential in the world of software development. This includes Agile methodologies, DevOps culture, Java and its frameworks such as Hibernate, JPA, Spring, Spring Boot, etc., JS, CSS, HTML, etc.

If you have the ability to learn new technologies, then you should definitely check out our full list of free online courses. If you have questions in this article about “C program for prime numbers” or suggestions for us, please mention them in the comments box and our experts will answer them as soon as possible.

Enjoyable learning!