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 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
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”.
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 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
EndImplementing 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.
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 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;
}
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).
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.
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
EndImplementing 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
EndImplementing 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.
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.
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 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!