Detect or Check Prime Number Program in C language

Spread the love

Different-ways-to-check-prime-number-program

Program Introduction:

The Check prime number program should check or detect whether the given number is a prime number or not a prime number.

Here are couple of examples.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

Example 3:

Input:

Output:

Checking Prime number Program logic:

Any positive number which is divisible by 1 (one) and itself is called Prime Number.

Let’s take ‘n’ as a input number.

So the main idea is to divide the given number by all numbers from 2 to n-1and see if the number is perfectly divisible by any of the numbers between 2 to n-1.

Perfectly divisible means, We should get zero as the remainder after the division. Here is an example.

Example : 10/2 ( Which gives us zero (0) as the remainder )

If a number(2) which perfectly divides any other number(10) then we call that number(2) a factor of 10. So In the above example, 2 is a factor of 10.

Prime Number is such a number, It’s factors are only one (1)and the number itself. It won’t have any other factors.

If Given Number is perfectly divisible by at least one number from 2to n-1. In other words, if a given number has any factor between 2 to n-1, Then the given number is not a Prime number.

If Given Number is not divisible(perfectly) by any number between 2 to n-1. Then It is a Prime Number. As it is only divisible by itself and 1.


There are multiple ways to check whether the given number is prime or not. We are going to discuss three different ways in this program

  • Method 1 – By checking for factors of the given number(n) from 2 to n-1.
  • Method 2 – By checking for factors of the given number(n) from 2 to n/2.
  • Method 3 – By checking for factors of the number(n) from 2 to sqrt(n). This method is the most efficient method to check prime numbers.

Let’s start with the method 1.

Method 1: Detect prime number by checking for factors from 2 to n-1 numbers:

In this method, We are going to divide the given number( n) with all numbers from 2to n-1.So if the given number is prime, It should not have any factors from the numbers 2 to n-1.

Here is the logic of the program. We are going to take one variable called counter and initialize it with zero (0). We will go through all numbers from 2to n-1. At each iteration(variable 'i' ), we will check if the given number ( n) is perfectly divisible by variable 'i'. And if it is perfectly divisible then we will increase the counter by 1. We will repeat this process for all iterations.

Finally, we check the value of the counter. If the counter value is greater than Zero(0) then The given number ( n) has factor(s). So The number( n) is not a prime number.

If the counter value is equal to zero(0). Then Number( n) is a Prime Number.

Method 1: Check or Detect prime number program:

Program Output:

We are using the GCC compiler to compile the code.

In the above program, We are unnecessarily looping till the n-1. Which can slow down the execution. So try to improve the above program.

Method 1 (Modified for improving the Performance):

We can slightly modify the above program to improve the performance. In the above program, We are not stopping the loop once we found the factor. The prime number should not have any factors. So we can stop the for loop once we found the first factor Instead of iterating through all the numbers ( 2to n-1).

📢 Stop the Loop once we found the first Factor of ‘n’. Because prime number don’t have any factors from 2 to n-1.

Let’s re-write above program to stop once we found the factor.

Modified Method 1: Check Prime Number:

Program Output:

Method 2: Detect prime number by checking for factors from 2 to n/2 numbers:

This method is also similar to the above method(modified method 1). But we are not going to check all numbers from 2 to n-1for the factors.

It will be enough to check from 2 to n/2 numbers to find the factors. If we found any factor then the number is not a prime number.

So this method is little fast compared the above method.

In this method, We are going to divide the given number( n) with all numbers from 2to n/2.So if the given number is prime, It should not have any factors from the numbers 2 to n/2.

Program logic is the same as the above method. The only change is in the number of iteration. Now In the worst case, We will only loop for 2to n/2 times.

Method 2: Check or Detect prime number program:

The program will try to find the factors of the given number 'n' . We will start from 2 and continue till n/2. And we will stop iterating after finding the first factor.

In the worst case, If we don’t find any factor for a given number, Then we will iterate till n/2 number.

Program Output:

Method 3: Detect prime number by checking for factors from 2 to Square root of n (sqrt(n)) numbers:

This method is also similar to the above methods. But we are not going to check all numbers from 2 to n-1 or 2 to n/2 for finding the factors.

We are going to check only the numbers from 2 to sqrt(n) numbers only. The sqrt(n) means the square root of the number n.

As we know the square root of n is much smaller than the n or n/2. In the worst case, The number of iteration we take for the sqrt(n) method is very less compared above two methods.

The composite Number rule says, If a number is not a prime number ( i.e Composite Number), It should contain at least one factor in the numbers from 2 to the square root of that number ( sqrt(n)). That means, If any number(n) doesn’t have any factor from 2 to square root of that number ( Sqrt(n)), Then we call that number( n) as a prime number.

For example. If ‘n’ is 10000, In the worst case (let’s assume we don’t found any factors for 10000)

  • Method 1 will take around n iterations. That is 10000 Iterations
  • Method 2 will take around n/2 iterations. That is 5000 Iterations.
  • Method 3 will take around sqrt(n) iterations. That is only 100 Iterations.

If you see Method 3, Prime number check with Square root is very very efficient for larger values. So whenever possible use the sqrt method.

As you can see this Square root ( sqrt(n)) way of calculating the prime number is the fastest and efficient way to check the prime number.

lets convert above logic into the code.

Method 3: Check prime number using square root program:

Here we are going to use the c programming languages in-builtSquare root( sqrt() ) Function.

But the Square root function is available under math.h headerfile. So we need to include the <math.h> headerfile to our program.

Program Output:

As we are using sqrt()function of math.h library. Few compilers might need us to externally provide the library path while compiling the program. So that compiler will look for the function in the provided library which will avoid the linking error.

Here I am including the math library by providing the -lmoption while compiling the program.

We have discussed more about sqrt function in the following article, Please look for more info – Prime Number program in C using sqrt (square root ) Function – SillyCodes

Conclusion:

In this article, We have looked at different ways to check if the given number is a prime number or not. The most efficient way is to use the square root method.

Related Math Programs:

References:

Venkat

Hi Guys, I am Venkatesh. I am a programmer and an Open Source enthusiast. I write about programming and technology on this blog.

You may also like...

Leave a Reply