C Language Series #144: Check Prime Number in C
Welcome to another installment in our C Language Series! In this post, we'll delve into a fundamental programming problem: determining if a given number is a prime number. This seemingly simple task is an excellent way to practice core C concepts like loops, conditional statements, and even introduces us to basic algorithm optimization.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For instance, 2, 3, 5, 7, 11 are prime numbers. Numbers like 4 (divisible by 2), 6 (divisible by 2, 3), or 9 (divisible by 3) are not prime; they are called composite numbers.
The Basic Approach: Iterating from 2 to `n-1`
The most straightforward way to check for primality is to try dividing the given number `n` by every integer from 2 up to `n-1`. If `n` is perfectly divisible by any of these numbers (i.e., the remainder is 0), then `n` is not prime. If no such divisor is found, `n` is prime.
Edge Cases to Consider:
- Numbers less than or equal to 1 are not prime by definition.
- The number 2 is the only even prime number.
Code Example: Basic Prime Check
Let's implement this basic logic in C:
#include <stdio.h>
int main() {
int n, i, isPrime = 1; // Assume it's prime initially
printf("Enter a positive integer: ");
scanf("%d", &n);
// Handle edge cases
if (n <= 1) {
isPrime = 0; // Numbers <= 1 are not prime
} else {
// Loop from 2 up to n-1
for (i = 2; i < n; i++) {
if (n % i == 0) {
isPrime = 0; // Found a divisor, so it's not prime
break; // No need to check further
}
}
}
if (isPrime) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
return 0;
}
Explanation:
- We initialize
isPrimeto1(true) and set it to0(false) if a divisor is found. - The loop
for (i = 2; i < n; i++)checks for divisibility. - If
n % i == 0, it meansidividesnevenly, sonis not prime, and webreakthe loop.
Optimization 1: Checking Divisors Up to `n/2`
Consider a number `n`. If `n` has a divisor `i` greater than `n/2` (and not equal to `n`), then `n` would also have a corresponding divisor `j = n/i` which would be less than `n/2`. For example, if `n=10`, divisors are 2 and 5. Here, 5 is greater than `n/2` (5 > 10/2). Its pair is 2, which is less than `n/2`. This implies we only need to check for divisors up to `n/2`.
#include <stdio.h>
int main() {
int n, i, isPrime = 1;
printf("Enter a positive integer: ");
scanf("%d", &n);
if (n <= 1) {
isPrime = 0;
} else if (n == 2) { // 2 is prime
isPrime = 1;
} else if (n % 2 == 0) { // All other even numbers are not prime
isPrime = 0;
} else {
// Loop from 3 up to n/2, only odd numbers
for (i = 3; i <= n / 2; i += 2) { // Increment by 2 to check only odd divisors
if (n % i == 0) {
isPrime = 0;
break;
}
}
}
if (isPrime) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
return 0;
}
Improvement: This version first handles `n=2` and other even numbers. Then, for odd `n`, it checks only odd divisors from 3 up to `n/2`, effectively halving the number of iterations in the loop compared to the basic approach.
Optimization 2: Checking Divisors Up to `sqrt(n)`
This is the most common and efficient optimization for checking primality of a single number. The logic is based on the property: if a number `n` has a divisor `d` greater than its square root (`sqrt(n)`), then it must also have a divisor `n/d` which is less than its square root.
For example, if `n = 100`, `sqrt(n) = 10`. If we find a divisor `20` (which is > 10), then `100/20 = 5` is also a divisor (which is < 10). So, if we don't find any divisors up to `sqrt(n)`, we won't find any beyond it either.
#include <stdio.h>
#include <math.h> // Required for sqrt() function
int main() {
int n, i, isPrime = 1;
printf("Enter a positive integer: ");
scanf("%d", &n);
if (n <= 1) {
isPrime = 0;
} else if (n == 2) {
isPrime = 1;
} else if (n % 2 == 0) {
isPrime = 0; // All even numbers except 2 are not prime
} else {
// Check for odd divisors from 3 up to sqrt(n)
for (i = 3; i <= sqrt(n); i += 2) {
if (n % i == 0) {
isPrime = 0;
break;
}
}
}
if (isPrime) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
return 0;
}
Key Points for this Optimization:
- Include
<math.h>to use thesqrt()function. - Remember to link with the math library during compilation (e.g.,
gcc your_program.c -o your_program -lm). - This significantly reduces the number of iterations, especially for large numbers, making it much more efficient.
Encapsulating Logic in a Function
For better code organization and reusability, it's good practice to wrap the prime-checking logic into a dedicated function.
#include <stdio.h>
#include <math.h> // For sqrt()
/**
* @brief Checks if a given integer is a prime number.
* @param num The integer to check.
* @return 1 if the number is prime, 0 otherwise.
*/
int isPrime(int num) {
if (num <= 1) {
return 0; // Numbers <= 1 are not prime
}
if (num == 2) {
return 1; // 2 is the only even prime number
}
if (num % 2 == 0) {
return 0; // All other even numbers are not prime
}
// Check for odd divisors from 3 up to sqrt(num)
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) {
return 0; // Found a divisor, so it's not prime
}
}
return 1; // No divisors found, it's prime
}
int main() {
int number;
printf("Enter an integer to check for primality: ");
scanf("%d", &number);
if (isPrime(number)) {
printf("%d is a prime number.\n", number);
} else {
printf("%d is not a prime number.\n", number);
}
// Example usage for multiple numbers
printf("\nChecking numbers from 1 to 20:\n");
for (int i = 1; i <= 20; i++) {
if (isPrime(i)) {
printf("%d is prime.\n", i);
} else {
printf("%d is not prime.\n", i);
}
}
return 0;
}
This organized approach allows you to easily check primality for any number throughout your program without rewriting the logic.
Conclusion
Checking for prime numbers is a classic problem that teaches valuable lessons in algorithm design and optimization. We started with a basic brute-force method, then improved its efficiency by reducing the search space to `n/2`, and finally to `sqrt(n)`. Understanding these optimizations is crucial for writing efficient code, especially when dealing with larger inputs.
Keep experimenting with these examples, and try to think about other ways you might further optimize this particular problem or apply these optimization techniques to other computational challenges!