Prime Number Program in C
Last Updated :
11 Oct, 2024
A prime number is a natural number greater than 1 and is completely divisible only by 1 and itself. In this article, we will learn how to check whether the given number is a prime number or not in C.
Examples
Input: n = 29
Output: 29 is prime
Explanation: 29 has no divisors other than 1 and 29 itself. Hence, it is a prime number.
Input: n = 15
Output: 15 is NOT prime
Explanation: 15 has divisors other than 1 and 15 (i.e., 3 and 5). Hence, it is not a prime number.
Check for Prime Number in C
We can check whether the number is prime or not by iterating in the range from 1 to n using loops. We will count the number of divisors. If there are more than 2 divisor (including 1 and n) then the given number n is not prime, else n is prime. This method is known as trial division method. Also, If you’re looking to improve your problem-solving skills and apply them to data structures, the C Programming Course Online with Data Structures provides similar exercises with detailed solutions.
Code Implementation
C
// C Program to check for prime number using
// Simple Trial Division
#include <stdbool.h>
#include <stdio.h>
int main() {
int n = 29;
int cnt = 0;
// If number is less than/equal to 1,
// it is not prime
if (n <= 1)
printf("%d is NOT prime\n", n);
else {
// Check for divisors from 1 to n
for (int i = 1; i <= n; i++) {
// Check how many number is divisible
// by n
if (n % i == 0)
cnt++;
}
// If n is divisible by more than 2 numbers
// then it is not prime
if (cnt > 2)
printf("%d is NOT prime\n", n);
// else it is prime
else
printf("%d is prime", n);
}
return 0;
}
Time Complexity: O(n), where n is the given number.
Auxiliary Complexity: O(1)
Optimized Approach
To optimize the above approach, we use a mathematical property which states that, “The smallest factor of a number greater than one cannot be greater than the square root of that number.”
Using this, we can reduce the numbers to be checked from N to √N making it much more efficient than above approach.
Code Implementation
C
// C Program to Check if a Number is Prime
// using Square Root
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
int main() {
int n = 29;
int cnt = 0;
// If number is less than/equal to 1,
// it is not prime
if (n <= 1)
printf("%d is NOT prime\n", n);
else {
// Check how many numbers divide n in
// range 2 to sqrt(n)
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
cnt++;
}
// if cnt is greater than 0 then n is
// not prime
if (cnt > 0)
printf("%d is NOT prime\n", n);
// else n is prime
else
printf("%d is prime\n", n);
}
return 0;
}
Time Complexity: O(√n), where n is the given number
Auxiliary Space: O(1)