C program to check if a number is a prime or not has been shown here. A positive number $n$ is called a prime, if it does not have any divisor except $1$ and $n$. For example if $n = 13$, it is prime but if $n = 10$, it is not prime as $10$ is divisible by $2$ and $5$ apart from $1$ and $10$. The algorithm, pseudocode and time complexity of the program have been shown below.
Page content(s):
1. Algorithm to check if a number is a prime or not
1. Take a positive number n as input.
2. Check for each i $\in$ [2, $\sqrt{n}$], if n is divisible by i
3. If step 2 is true for atleast one i, then n is not a prime.
4. If step 2 is false for each i, then n is a prime.
2. Pseudocode to check if a number is a prime or not
Input : A postive number $n$
Output : $n$ is a prime or not a prime
1. Procedure checkPrime($n$):
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14. End Procedure
3. Time complexity to check if a number is a prime or not
Time Complexity: O($\sqrt{n}$)
Where n is the input number.
4. C Program & output to check if a number is a prime or not using iteration
/********************************* alphabetacoder.com C program to check if a number is a prime or not using iteration ***********************************/ #include <stdio.h> #include <math.h> int main() { // declare variables int n, i, flag = 0; // take input of the number printf("Enter the number = "); scanf("%d", & n); //check if n is a prime or not //If n has divisor between 2 and // square root of n, then // n is not prime else n is prime for (i = 2; i <= sqrt(n); i++) { if (n % i == 0) { flag = 1; // mark as not prime break; // exit from loop } } // dispay the result if (n == 0 || n == 1) printf("%d is neither a prime nor a composite!", n); else { if (flag == 0) printf("%d is a prime!", n); else printf("%d is not a prime!", n); } return 0; }
Output
Case 1:
Enter the number = 13
13 is a prime!
Case 2:
Enter the number = 1
1 is neither a prime nor a composite!
Case 3:
Enter the number = 50
50 is not a prime!
5. C Program & output to check if a number is a prime or not using recursion
/********************************* alphabetacoder.com C program to check if a number is a prime or not using recursion ***********************************/ #include <stdio.h> #include <math.h> // recursive function to check // if a number is prime or not // check divisor upto sqrt(num) int check_prime(int num, int i) { // return 1, as num is prime if (i > sqrt(num)) return 1; // return 0, as num is not prime if (num % i == 0) return 0; // call function return check_prime(num, i + 1); } int main() { // declare variables int n, flag = 0; // take input of the number printf("Enter the number = "); scanf("%d", & n); //check if n is a prime or not // by calling the function // if the function returns 1, // it is considered prime else // it is considered not prime if (n == 0 || n == 1) printf("%d is neither a prime nor a composite!", n); else { if (check_prime(n, 2)) printf("%d is a prime!", n); else printf("%d is not a prime!", n); } return 0; }
Output
Case 1:
Enter the number = 97
97 is a prime!
Case 2:
Enter the number = 0
0 is neither a prime nor a composite!
Case 3:
Enter the number = 36
36 is not a prime!