Master Prime Numbers in C: Tutorial with Sample Code | Simplilearn (2023)

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

Also Read: Use of C Language

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

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

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.

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;

}

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

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;

}

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;

}

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.

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

}

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.

Ranked No.1 Best Coding Bootcamp, our Post Graduate Program in Full Stack Web Development, can help you accelerate your career as a software developer. Enroll 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.

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!