Check for Prime Number using Simple Method
In this method, we will check if any number between 2 to (N/2) can divide N completely. If such a number exists, it means that the number N is not a prime number as it is divisible by a number other than 1 and itself.
Note: We take (N/2) as the upper limit because there are no numbers between (N/2) and N that can divide N completely.
C Program to Check Prime Number Using Simple Approach
// C Program to check for prime number using Simple Approach
#include <stdio.h>
// Function to check prime number
void checkPrime(int N)
{
// initially, flag is set to true or 1
int flag = 1;
// loop to iterate through 2 to N/2
for (int i = 2; i <= N / 2; i++) {
// if N is perfectly divisible by i
// flag is set to 0 i.e false
if (N % i == 0) {
flag = 0;
break;
}
}
if (flag) {
printf("The number %d is a Prime Number\n", N);
}
else {
printf("The number %d is not a Prime Number\n", N);
}
return;
}
// driver code
int main()
{
int N = 546;
checkPrime(N);
return 0;
}
Output
The number 546 is not a Prime Number
Time Complexity: O(n), where n is the given number.
Space Complexity: O(1)
Prime Number Program in C
A prime number is a natural number greater than 1 that is completely divisible only by 1 and itself. For example, 2, 3, 5, 7, 11, etc. are the first few prime numbers.
In this article, we will explore a few prime number programs in C to check whether the given number is a prime number or not.
We can check if a number is prime or not in C using two methods:
- Simple Method
- Using sqrt(N)