YouTip

## C Program to Check and Find Prime Numbers A **prime number** is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number cannot be formed by multiplying two smaller natural numbers. Examples of prime numbers include 2, 3, 5, 7, 11, and so on. Numbers that are not prime are called composite numbers. In this tutorial, you will learn how to write C programs to: 1. Check whether a given number is prime. 2. Find all prime numbers between two given integers. 3. Find prime numbers between two intervals using a custom function. --- ## 1. Check Whether a Number is Prime This program takes a positive integer from the user and checks whether it is a prime number. ### Algorithm To determine if a number $n$ is prime, we check if it is divisible by any number from $2$ up to $n/2$. If we find any divisor in this range, the number is not prime (we set a flag to `1` and exit the loop). If no divisors are found, and the number is greater than 1, it is a prime number. ### C Source Code ```c #include int main() { int n, i, flag = 0; printf("Enter a positive integer: "); scanf("%d", &n); // Loop to check divisibility from 2 up to n/2 for(i = 2; i <= n / 2; ++i) { // If n is divisible by i, it is not a prime number if(n % i == 0) { flag = 1; break; } } // 0 and 1 are not prime numbers if(n <= 1) { flag = 1; } if (flag == 0) printf("%d is a prime number.\n", n); else printf("%d is not a prime number.\n", n); return 0; } ``` ### Output ```text Enter a positive integer: 29 29 is a prime number. ``` --- ## 2. Find Prime Numbers Between Two Intervals This program displays all prime numbers within a user-specified range (between `low` and `high`). ### C Source Code ```c #include int main() { int low, high, i, flag; printf("Enter two integers (intervals): "); scanf("%d %d", &low, &high); printf("Prime numbers between %d and %d are: ", low, high); while (low < high) { flag = 0; // Skip numbers less than or equal to 1 as they are not prime if (low <= 1) { ++low; continue; } // Check if the current value of 'low' is prime for(i = 2; i <= low / 2; ++i) { if(low % i == 0) { flag = 1; break; } } if (flag == 0) printf("%d ", low); ++low; } printf("\n"); return 0; } ``` ### Output ```text Enter two integers (intervals): 100 200 Prime numbers between 100 and 200 are: 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 ``` --- ## 3. Find Prime Numbers Between Intervals Using a Function For cleaner and more modular code, we can separate the prime-checking logic into a user-defined function called `checkPrimeNumber()`. ### C Source Code ```c #include // Function prototype int checkPrimeNumber(int n); int main() { int n1, n2, i, flag; printf("Enter two positive integers: "); scanf("%d %d", &n1, &n2); printf("Prime numbers between %d and %d are: ", n1, n2); // Loop through the range (excluding the boundary numbers themselves) for(i = n1 + 1; i < n2; ++i) { // Check if i is a prime number flag = checkPrimeNumber(i); if(flag == 1) printf("%d ", i); } printf("\n"); return 0; } // User-defined function to check prime number // Returns 1 if prime, 0 if not prime int checkPrimeNumber(int n) { int j, flag = 1; if (n <= 1) { return 0; // Numbers <= 1 are not prime } for(j = 2; j <= n / 2; ++j) { if (n % j == 0) { flag = 0; break; } } return flag; } ``` ### Output ```text Enter two positive integers: 10 30 Prime numbers between 10 and 30 are: 11 13 17 19 23 29 ``` --- ## Performance Considerations * **Loop Limit Optimization**: In the examples above, the loop runs up to `n / 2`. You can optimize this further by running the loop up to the square root of $n$ ($\sqrt{n}$). If a number $n$ has a factor larger than $\sqrt{n}$, it must also have a matching factor smaller than $\sqrt{n}$. * **Handling Small Numbers**: Always ensure your code explicitly handles numbers less than or equal to `1` (such as `0`, `1`, and negative numbers), as they are mathematically classified as non-prime.