A natural number that is divisible only by itself and 1 is known as a prime number. In short, we can say that it has two factors, which are 1 and the number itself. All those numbers that are not prime are called composite numbers.
A prime number can be represented as a product of two numbers. For example, we can consider 3 sone can be product of two numbers, 1 and 3, itself, i.e, 3*1. Irrespective of this composite number like 8 can be written with 2 variations, i.e, 8*1 and 2*4.
The chart mentioned below shows prime numbers between 1 - 100. This will help understand the further blog. Explore more on the right and simple language platform.
A C programfor prime numbers using a for loop is :
The algorithm ( steps ) to find a prime number using a C program is mentioned below :
Step 1:Take the number you want as input
Step 2: Initialise a temporary variable to 0.
Step 3:Start iterating by using a for loop from 2 to number/2.
Step 4:Increment the temporary variable if the number is divisible by the loop iterator.
Step 5:If temporary is equal to 0, then the program has to return “ Number is Prime “; else return “ Number is not prime “.
See below the Pseudocode to find whether the number is prime using a 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
A C program is implemented below using a for loop for prime numbers :
#include
int main()
{
int i, num, temp = 0;
//Read input from the user.
printf("Enter any numb to Check for Prime: ");
scanf("%d", &num);
// iterate up to n/2.
for (i = 2; i <= 0 num 2; i++) { check if is divisible by any number. (num % i="=" 0) temp++; break; } for the value of temp and num. (temp="=" && !="1)" printf("%d a prime number", num); else not return 0; < pre>
In the above program, we can see that the for loop is iterating from a range of 2 to n/2. Where n is the input number in this program. We can keep on checking every number till n/2 if this divides the number. If you find any multiple of n, then update the value of the temporary After this, you will see that the program returns “Prime” and “Not Prime”.
Time complexity : O(n)
As we can see that the loop is iterating from 2 to n/2, then the time complexity of the worst case possible is O(n). Here, n is the input element in the program.
Space complexity : O(1)
This program simply means not using an extra auxiliary space. So, only constant space will be used. This simply means space complexity is O(1).
The main reason for iterating this loop till n/2
Many of us have questions about why we are iterating the loop till n/2 instead of n. What is the reason for leaving the other half of it? Let's understand this with the help. Of examples. Consider different factors of the integer 12. The different factors are 1,2,3,4,6,12, etc. Here you can observe that after the number 12/2, i.e, 6. There is only one factor left, that is simply the number itself, which is 12 in this case. All this is simply true for all integers.
Now consider a prime number that is 17. The main factors of this are 1 and 17. After dividing 17/2, i e 8.5, there is simply only one factor, 17. So, if you want to find out if a number is prime or not, one factor is just enough. Finding this one factor is possible in the first half, as we can see that only one factor is there in the second half, and this is the number itself.
Using while loop below is C program for prime numbers
An algorithm to find prime numbers using the C programming language
Step 1:Take the number you want as input
Step 2: Initialise a temporary variable to 0.
Step 3:Initialise the iterator variable loop value to 2.
Step 4:Iterate the loop using a while condition with loop<= 2 number < li>
Step 5:If this number is divisible by the loop iterator, then just increment a temporary variable
Step 6: If this temp is equal to 0, then return “Number is prime”; else “Number is not prime”.
Pseudocode to find a prime number using a while loop condition
Start
Input num
Initialize variable temp = 0
Initialize loop = 2
WHILE loop <= 0 2 num if is divisible by loop increment temp end while equal to return “num prime” else not < pre>
Below is the implementation of a C program for prime numbers using a while loop
#include
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 <= 0 num 2) { check if is divisible by any number. (num % i="=" 0) temp++; break; } incrementation i++; for the value of temp and num. (temp="=" && !="1)" printf("%d a prime number", num); else not return 0; < pre>
In the above program, we have implemented a while loop instead of a for loop. The logic for both programs using while and for loops is the same.
Time complexity : O(n)
The loop present in the program runs from 2 to n/2, so the time complexity for the worst-case scenario will be O(n). Here is the input element.
Space complexity : O(1)
In this kind of program, only constant space is being used for some of the variables. We can see that space complexity is O(1).
Below is the C program for all the prime numbers using functions
Algorithm to find prime numbers :
Step 1:Firstly, define a function that will accept an integer num.
Step 2: Later, initialise a variable named temp to 0.
Step 3:Start iterating a form from 2 to num/2.
Step 4:Increment temporarily when num is divisible by the loop iterator.
Step 5:Return number.
Step 6: In the main function, if the temp function is equal to 0, then the program should return “Num is prime;” else return “Num is not prime”.
Here is the Pseudocode to find prime numbers using loop 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 a C program related to prime numbers using functions
#include
// function to check if
//The Theer is prime or not.
int find_Prime(int num)
{
int i, temp = 0;
// iterate up to num/2.
for (i = 2; i <= 0 num 2; i++) { if the number has factors, update temp. (num % i="=" 0) temp++; } return temp; int main() num, temp="0;" printf("enter any to check for prime: "); scanf("%d", &num); function call (temp="=" && !="1)" printf("\n %d is a prime number", num); else not 0; < pre>
Time Complexity: O(n)
The above program has a function that has only one for loop. This runs from 2 to n/2. We can see that in the worst case, this time complexity will be O(n).
Space Complexity: O(1)
Not a single extra space is used over here. The function will use only constant space, which will help in storing variables. So, space complexity will be O(1).
C program for prime numbers using recursion
An algorithm to find out prime numbers by using this
Step 1:Start by defining a recursive function that will be an integer num.
Step 2: Later, initialise a variable “i” to 2.
Step 3:If this number is equal to zero or 1, then the program should return false.
Step 4:If this number is equal to “I,” then the truth should be returned.
Step 5: Now increment “I”.
Step 6:Recursively start by calling your function and passing num as an argument.
Here is Pseudocode to find a 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 a C program for Prime Numbers Using Recursion
#include
#include
// 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;
}
There is a recursive approach to finding the prime numbers. In the program, a recursive function find_Prime is created that will simply check whether a number is divisible by any of the numbers. If this is the case, then return false; el, the recursive call will be made. This process will keep on repeating till a multiple of num is found.
Time Complexity: O(n)
The function is just calling itself recursively several times. Until a factor is found or a particular condition is satisfied, this will keep on going. Therefore, the time complexity observed here is O(n).
Space Complexity: O(n)
The n calls that are made by the recursive function will be stored in the stack, which will consume memory. So the space complexity of the recursive approach will be O(n).
C Program for Prime Numbers: Optimized Method
Algorithm to Find a Prime Number
Step 1:Take a number.as input.
Step 2: Initialise a variable temp to the value 1.
Step 3:Start iterating a for loop from 2 to sqrt(num).
Step 4:If num is divisible by a loop iterator, then update a temp value to 0.
Step 5:If the temp is equal. To 1, then return “Num is prime”; else return Num is not prime”.
Pseudocode to Find a 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
Below C program implemented for the prime numbers optimised method.
#include
#include
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 sqrt of num.
for (i = 2; i <= 1 sqrt(num); i++) { check if num is divisible by any number. (num % i="=" 0) update temp. temp="0;" break; } every number and not prime. <="1)" (temp="=" 1) printf("%d a prime number", num); else return 0; pre>
In the above program optimised solution is used to check whether a number is prime or not. Here, instead of iterating a loop till the number itself, so iteration will be done till sqrt n. This is possible because the smallest of a particular number that is greater than 1 cannot be greater than the square root of a particular number. For example, the smallest factor among all is 2, which is not greater than sqrt 64.
Time complexity : O(n1/2)
This is just because the for loop is simply iterating from 2 to the square root of. Here, n is the input element.
Space complexity : O(1)
In this whole program, no extra space is being used. Only a constant auxiliary type of space will be used to store the variables. In this way, iteration will be done in a particular place.
C Program for Prime Numbers Within a Range
An algorithm to find a Prime Number using this
Step 1:Take the range value left and right as input.
Step 2: Initialise a loop iterator num to the left
Step 3:Later, iterate the for loop from left to right.
Step 4:Here, iterate the for loop from 2 to num/2.
Step 5:Now, Initialise variable temp to 0.
Step 6:If num is divisible by the loop iterator, then the program should increment temp.
step 7: If temp has a value equal to 0, then return “Num. is Prime”; else program will return “Num is not Prime”.
Pseudocode to Find a 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
Implementation of a C Program for Prime Numbers Within a Range
#include
int main()
{
int i, num, temp, sum = 0, left, right;
Read the values of the range from the user.
printf("Enter the left & right Values: ");
scanf("%d %d", &left, & right);
// iterate “for” loop within the given range.
for (num = left; num <= 0 right; num++) { temp="0;" for loop to check the prime numbers. (i="2;" i <="num" 2; i++) if num is divisible by any number. (num % 0) temp++; break; } values of and num. (temp="=" && !="1)" sum="sum" + num; printf("sum numbers between %d left, right, sum); return 0; pre>
In the above programs, the sum of the prime numbers is printed in the given range. Users will read the starting and ending points. A nested for loop is used for iteration. The outer loop will run from left to right, and the inner loop will run n/2 for each iteration of the outer loop.
Time Complexity: O((right-left)*num)
In this number is the input number, while left and right are the starting and ending points of a given range. So a nested loop is used where the outer loop will iterate from left to right, and the inner loop will iterate from 2 up to n/2. So we can see that the puyer loop will run right-left times and the inner loop will iterate num times.
Space Complexity: O(1)
No kind of space is being used over here. Constant space is used to store the variables. So, space complexity will be O(1).
C Program for Prime Numbers Using Sieve of Eratosthenes
Algorithm to Find a Prime Number
Step 1:Take only a natural number as input.
Step 2: Later on, create a Boolean array is prime[] and then you can initialise all its elements to 1. The assumption is done initially, all events are prime.
Step 3: If a particular element k is equal to 1 or true, then mark all its multiples that are greater than k2 to 0.
Step 4:Repeat step 2, princess, for all unmarked ones that are equal to 1 or true, all elements until sqrt of 1 will be reached
Step 5:Then iterate over the Boolean array isPrime [], if this particular isPrime[I] is equal to 1, then return “Num is prime”; else return” Num is not prime”.
Pseudocode to Find Prime Numbers Using the Sieve of Eratosthenes
Start
Input num
Create a boolean array isPrime[]
Initialize all elements of isPrime[] to 1
FOR k = 2 to k2 <= 1 num if isprime[k] is equal to for i="k2" <="num" isprime[i]="0" end loop="2" isprime[loop] print "isprime[loop] prime" pre>
Implementation of a C Program for Prime Numbers Using Sieve of Eratosthenes
#include
#include
#include
// function to find all the
// prime numbers from 1 to num.
void find_Prime(int num)
{
//Initialize all elements of
//The array is Primis 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 a prime. (isprime[k]="=" true) update all the multiples of k as false, starting from it's square number for (int i="k" * k; <="num;" +="k)" isprime[i]="false;" } print prime numbers. (isprime[k]) printf("%d, ", k); int main() num="30;" printf("following are numbers smaller "); than or equal to num); printf("\n"); function call find_prime(num); return 0; pre>
Time Complexity: O(n*log(log(n)))
The time complexity is assumed to be constant for marking all nonprime numbers. To find the time complexity to run the loop until k, the equation comes. This equation is solved by using Harmonic Progression and Taylor series expansion, Euler’s Formula, followed by summation and simplification. Later final result is deducted, which is equal to n * log(log(n)).
Space Complexity: O(n)
Space consumed by the Boolean array is Pr,im ss t is declared to be of size equal to the number. So time complexity is O(n), and n is the input element over here.
Conclusion :
In this blog, all types of C programs were illustrated for prime numbers. Explore more such things, learn from Uncodemy courses, and ace in the future. The right path will take you towards the right destination, so follow us for more updates and stay informed in this tech-savvy, ever-changing world. Feel free to contact and get all your queries solved with great learning.
Placed Students
Our Clients
Partners
Uncodemy Learning Platform
Uncodemy Free Premium Features
Smart Learning System
Personalized learning paths with interactive materials and progress tracking for optimal learning experience.
