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.
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:
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:
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.
Also Read: Prime Number Programming In Python
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:
Let’s discuss these approaches in detail with the code examples, their explanation, and the respective output of each example.
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:
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)
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:
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)
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:
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))
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:
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)
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:
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.
Book a free counselling session
Get a personalized career roadmap
Get tailored program recommendations
Explore industry trends and job opportunities
Programs tailored for your success
Popular
Data Science
Technology
Finance
Management
Future Tech
© 2024 Hero Vired. All rights reserved