In this article, you will learn C Program to Check Whether a Number is Prime or not using the efficient way.
A prime number is a positive natural number that is divisible only by 1 and itself. That means it can have only two factors 1 and the number itself. For example: 2, 3, 5, 7, 11, 13, 17.
The following C programming topics are the primary prerequisites for this example code :
Problem statement:
Given a positive integer num. You need to write a C program to check if the number is prime or not.
Solution:
I am dividing the solution into the following steps.
Step 1 → Take the number n.
Step 2 → Number should be greater than 1.
Step 3 → Divide the number n with (2, n-1) or (2, n/2) or (2, sqrt(n)).
Step 4 → If the number n is divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is not prime
Step 5 → If it is not divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is a prime number
// C program to check if a // number is prime #include <stdio.h> #include <math.h> int main() { int num, i, isPrimeNum = 1; //Ask user for input printf("Enter a number: = "); //Get the integer input from the user scanf("%d", &num); // -ve, 0 and 1 are not prime numbers // change isPrimeNum to 1 for non-prime number if ((num <= 0) || (num == 1)) { isPrimeNum = 0; } else { // Iterate from 2 to sqrt(num) for (i = 2; i <= sqrt(num); i++) { // If num is divisible by any number between // 2 and num/2, it is not prime if ((num % i) == 0) { isPrimeNum = 0; break; } } } //Now print the message if (isPrimeNum == 1) { printf("%d is a prime number\n", num); } else { printf("%d is not a prime number\n", num); } return 0; }
Output:
Enter a number: = 7 7 is a prime number
Explanation:
The above-mentioned C program to check whether a number is prime or not is an efficient way to check prime numbers.
Why I am saying this because here we only iterate through all the numbers starting from 2 to sqrt(N) beside that 2 to N.
As you know that prime number is only divisible by 1 and itself; so in each iteration, we check the number “num” is divisible by “i” or not by using the below code.
for (i = 2; i <= sqrt(num); i++) { // If num is divisible by any number between // 2 and num/2, it is not prime if ((num % i) == 0) { isPrimeNum = 0; break; } }
If “num” is perfectly divisible by “i“, num is not a prime number. Also marked the flag “isPrimeNum” is set to 1 and terminates the loop using the break statement. The default value of the flag isPrimeNum is 0.
Recommended Articles for you:
- find all prime numbers up to n using trial division and Sieve of Eratosthenes algorithm.
- C language character set.
- Elements of C Language.
- Data type in C language.
- Operators with Precedence and Associativity.
- C Program to find prime factors of a number.
- C Program to print Twin prime numbers between two ranges.