C Program To Check Prime Number By Creating a Function
Last Updated :
20 Aug, 2024
Write a C program that checks whether a given number is a prime number by creating a dedicated function. A dedication function is better when we want to use the code multiple times in the program without making any changes.
Example:
Input: N = 7
Output: Prime
Explanation: 7 has no divisors other than 1 and 7, so it is a prime number.
Input: N = 10
Output: Not Prime
Explanation: 10 is divisible by 1, 2, 5, and 10, so it is not a prime number.
Different Methods to Check Prime Numbers Using Function in C
1. Using Function for Trial Division Approach
The idea of this approach is to check the divisibility of the number N with each number from 2 to N−1. If it is completely divisible by any number, then it is not a prime number.
Implementation
C
// C Program to Check Prime Number using Simple Trial
// Division Approach
#include <stdio.h>
int isPrime(int N) {
// Check divisibility from 2 to N-1
for (int i = 2; i < N; i++) {
// If N is divisible by i, it is not a prime number
if (N % i == 0) {
return 0;
}
}
// If no divisors were found, N is a prime number
return 1;
}
int main() {
int N = 10;
printf("Is %d prime?\n", N);
// Check if the number is prime
if (isPrime(N)) {
printf("Yes\n");
}
else {
printf("No\n");
}
return 0;
}
Time Complexity: O(N)
Auxiliary Space: O(1)
2. Using Function for Optimized Trial Division Approach
In the above approach, we only need to check for factors up to the square root of N because if N is divisible by any number greater than its square root, then the quotient would be smaller than the square root and would have been checked already.
Implementation
C
// C Program to Check Prime Number using Square Root Optimized
// Trial Division Approach
#include <math.h>
#include <stdio.h>
int isPrime(int N) {
// Check divisibility from 2 to sqrt(N)
for (int i = 2; i <= sqrt(N); i++) {
// If N is divisible by i, it is not a prime number
if (N % i == 0) {
return 0;
}
}
// If no divisors were found, N is a prime number
return 1;
}
int main() {
int N = 10;
printf("Is %d prime?\n", N);
// Check if the number is prime
if (isPrime(N)) {
printf("Yes\n");
}
else {
printf("No\n");
}
return 0;
}
Time Complexity: O(√N)
Auxiliary Space: O(1)
Related Articles: