Home

Learning Hub

Articles

How to Check Prime Number Program in C?

Learning programming requires your fundamental mathematical concepts to be strong. One of the fundamentals of mathematics, particularly number theory, is a prime number. Any natural number larger than one that is not the product of two smaller natural numbers is known as a prime number. A prime number in simple terms is the one that is only divisible by 1 or by itself. 

In programming, finding whether a number is prime is a common problem. However, grasping the idea of loops, conditionals, and efficiency of algorithms may be easier if you first see an implementation of prime numbers using the C program. In this article, we will discuss different approaches to check whether or not a number is prime. While exploring different methods to accomplish this task, we will provide code snippets and detailed explanations enclosed within their syntax examples. Let’s begin.

What is a Prime Number?

A prime number is a number that is divisible by 1 and itself. A prime number contains two factors i.e., 1 and the number itself. For example, the first ten prime numbers include 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29. The numbers left after the prime number are known as composite numbers. Let’s see some facts about prime numbers:

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• There are infinite numbers of prime numbers
• The gap between two prime numbers can be short or long depending on the number.
• 2 is the smallest prime number in mathematics.
• We can use prime numbers larger than 3 as 6k+1 or 6k−1 (for some natural number k).
• Zero (0) and one (1) are not prime numbers.

Algorithm to Check Prime Number in C

Checking a prime number using a C program is simple and easy. Below is a detailed and generalised algorithm for checking if a number is prime or not in C:

1. Take an input number (a)
2. Base condition check:
   1. If a is less than 2, the number
      is not prime.
   2. If a is equal to 2, then it is
      a prime.
3. Check for the prime number:
   1. For numbers greater than 2,
      check divisibility from 2 up to a − 1. 
   2. If a is divisible by any number
      in this range, it is not a prime number.
4. If a is not divisible by any number in
   the given range, it is a prime number.

Pseudocode

Let’s now understand the pseudocode for the discussed algorithm that you can apply in C language and other languages. The pseudocode for checking if a number is prime or not in C:

Explanation:

In this pseudocode, we have outlined the basic algorithm to find whether a given number is a prime number or not.

• The algorithm has a function that takes an input parameter (a). 
• The function begins by checking if a is less than or equal to 1. 
• If true, it returns 0, indicating a is not prime. 
• If a is exactly 2, it returns 1, indicating a is prime. 
• For numbers greater than 2, the function iterates from 2 to a – 1. During each iteration, it checks if a is divisible by i using the modulo operator (%). 
• If true, it returns 0, indicating a is not prime. If the loop completes without finding any divisors, it returns 1, indicating a is prime.

Also Read: Prime Number Programming In Python

Approaches

In C language, there are various approaches by which you can check prime numbers in a C  program. We will discuss various approaches by which you can find whether a given number is prime or not:

• Using Range (Simple)
• Using Squareroot (Optimised)
• Using recursion
• Using Wilson’s Theorem
• Using Sieve of Eratosthenes

Let’s discuss these approaches in detail with the code examples, their explanation, and the respective output of each example.

• Using Range (Simple)

The simplest and easiest way to check a prime number in the C program is to check all  numbers from 2 to num – 1 (where num is the given input) and see if any of them divide num without leaving a remainder. If any of the numbers does it, then it is said to be a non-prime number.

Below is the algorithm for checking whether a number is prime or not using range:

1. If num is less than 2, it’s a non-prime number. 
2. Loop from 2 to num − 1. 
3. For each number in the loop, check if it divides num without leaving a remainder. 
4. If such a number is found, num is a non-prime number. 
5. If no such number is found, num is a prime number.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the simplest approach to find whether a number is prime. The method works by taking an input parameter num and looping through till n – 1. We then check if the input number ‘num’ after dividing by i gives 0, then return it as not a prime number. If it returns 1, then the number is a prime number.

Time Complexity: O(N)

Space Complexity: O(1)

• Using Squareroot (Optimised)

The square root of a number can also be used to check for prime numbers in the C program. This approach is an optimised version of the above approach as we reduce the number of checks. Here, the larger factor of num input must be a multiple of a smaller factor that is less than or equal to num​. Therefore, we only need to check divisibility up to num.

Below is the algorithm for checking whether a number is prime or not using a square root:

1. If num is less than 2, it’s a non-prime number. 
2. Loop from 2 to the square root of num. 
3. For each number in the loop, check if it divides num without leaving a remainder.
4. If such a number is found, num is a non-prime number. 
5. If no such number is found, num is a prime number.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using an optimised approach using square roots to find whether a number is prime. The method works by taking an input parameter num and looping through to the square root of num. We then check if the input num after dividing by i gives 0, then return it as not a prime number. If it returns 1, then the number is a prime number.

Time Complexity: O(sqrt(N)

Space Complexity: O(1)

• Using recursion

Recursion is also used to check prime numbers in the C program. It follows a clear and concise approach to finding whether the number is prime or not by using the divide-and-conquer approach. This approach breaks down the problem into smaller subproblems until a base case is reached.

Below is the algorithm for checking whether a number is prime or not using recursion:

1. The recursive function takes two parameters num (number to check for prime) and k (divisor to check). 
2. Apply base cases: 
   1. If num <= 1, return False and it is not prime.
   2. If k is equal to 1, return True, and all numbers greater than k are prime.
3. If num % k == 0, then return False, number is not prime.
4. The recursive function call continues, check Prime(num, k – 1) to check the next smaller divisor.
5. Finally, print the output.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the recursive approach to find whether a number is prime. The checkPrime function takes two parameters: the number num and a divisor k. It first checks if num is less than or equal to 1, returning 0 if true, indicating the number is not prime. If k is 1, it returns 1, indicating the number is prime. The function then checks if num is divisible by k; if so, it returns 0, indicating the number is not prime. If none of these conditions are met, the function calls itself with k-1, recursively checking all possible divisors. This continues until a divisor is found or all possibilities are exhausted, determining the primality of the number.

Time Complexity: O(sqrt(N))

Space Complexity: O(sqrt(N))

• Using Wilson’s Theorem

Wilson theorem is another algorithm that states that any prime number n divides (n-1)! + 1. The theorem states that a natural number n (greater than 1) is a prime if and only if: (n−1)! == −1 (mod n). 

Below is the algorithm for checking whether a number is prime or not using Wilson’s theorem:

1. We first compute the number num factorial using (num – 1)!.
2. Check if (num − 1)! == −1 (mod num) or (num-1)! % num == num – 1.
3. Now, if the above condition is true, then the number is prime, otherwise a non-prime.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using Wilson’s theorem to determine if a number is prime. The checkPrimeFact function calculates the factorial of num-1 and returns it. In the main function, the user is prompted to enter a number. If the number is less than or equal to 1, it is immediately declared not prime. For other numbers, the factorial of num-1 is computed, and the result is checked against Wilson’s Theorem condition: (num-1)! % num == num – 1. If true, the number is prime; otherwise, it is not.

Time Complexity: O(N)

Space Complexity: O(1)

• Using Sieve of Eratosthenes

Sieve of Eratosthenes is the most efficient algorithm for finding whether a number is a prime number or not. In this approach, a limit is set on which the algorithm works.

Below is the algorithm for checking whether a number is prime or not using the Sieve of Eratosthenes:

1. We have a boolean array prime[] where each index represents whether the number is prime or not.
2. Mark all non-prime numbers from 2 to the square root of num. 
3. For each prime number found, mark all of its multiples (starting from its square) as non-prime in the prime[].
4. After processing up to num​ , the numbers leftover are marked as true in the prime[] array and are said to be prime numbers.

Let’s see a detailed example now for checking whether a number is prime or not:

Code example:

Output:

Explanation:

In this example, we are using the Sieve of Eratosthenes approach to check for prime numbers. Here, in the example, we have a function sOfE that initialises an array prime where each element represents whether its index is a prime number. It iterates through numbers up to the square root of the limit, marking multiples of each prime as non-prime. In the main function, the user is prompted to enter a number. The checkPrime function checks if the number is prime by looking up the precomputed array. If the number is within the limit, it returns whether the number is prime based on the precomputed data.

Time Complexity: O(N log * (log N))

Space Complexity: O(N)

These are some of the common approaches to find whether a number is a prime number or not in C but there are more approaches that you can use to write this program. Now the choice between which approach to choose depends on various factors like the program complexity, time constraints, or any specific requirements.

In this article, we looked at a few different ways to determine whether a given number is prime. We looked at easy methods like the optimised square root method and range checking. We also explored some optimal and efficient algorithms like Wilson’s Theorem for prime checking, recursive methods, and the Sieve of Eratosthenes to efficiently compute prime numbers up to a predetermined threshold. We also discussed the time and space complexity of each approach.