How to find whether a given number is prime number?

prime number in c

A prime number is a positive natural number, whose value greater than 1 and it has only two factors 1 and the number itself. Either you can say that prime numbers only divided by itself and 1. Any positive natural number who is not a prime number is called a composite number.

For example,

2,3,5,7,11..
In the above example, 2 is the (smallest) prime number because it has only two factors 1 and 2.

Note: 1 is not a prime or composite number and 2 is the only even prime number.

Using the trial division we can check the prime number in C but it is a slow method to check the prime number. In which we need to check whether given number n is a multiple of any integer between 2 and the square root of n.

We can also use faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical.

 

Algorithm to check prime number using trial division method

START

Step 1 → Take the number n

Step 2 → Divide the number n with (2, n-1) or (2, n/2) or (2, sqrt(n)).

Step 3 → 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 4 → 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

STOP

 

Check Prime Number In C

Above I have discussed that there are many ways to find the prime number in C.  In this blog post, I will discuss only the trial division method for another algorithm I have written separate articles. So let see some C programs to check prime numbers using the trial division method.

 

Example Code 1:

In the below code to check prime number, we are checking that the given number n is a multiple of any integer between 2 and (n -1) or not. If the given number n is a multiple of any integer between 2 and (n -1), then n will be not a prime number.

#include <stdio.h>

#define PRIME_NUMBER  1

int isPrimeNumber(int number)
{
    int iLoop = 0;
    int iPrimeFlag = 1;
    //check for negative number and one
    if(number <= 1)
    {
        iPrimeFlag = 0;
    }
    else
    {
        for(iLoop = 2; iLoop < number; iLoop++)
        {
            // check prime number
            if((number % iLoop) == 0)
            {
                //update the flag when number is not prime
                iPrimeFlag = 0;
                break;
            }
        }
    }
    return iPrimeFlag;
}

int main()
{
    int iRetValue = 0;
    int number = 0;

    printf("Enter the number : ");
    scanf("%d",&number);

    iRetValue = isPrimeNumber(number);
    //Check for prime number
    if (iRetValue == PRIME_NUMBER)
    {
        printf("\n\n%d is prime number..\n\n", number);
    }
    else
    {
        printf("\n\n%d is not a prime number..\n\n", number);
    }
    return 0;
}

Output:

prime number in c

 

 

prime number in c

 

 

 

 

Example 2:

In the below code to check prime number, we are checking that the given number n is a multiple of any integer between 2 and (n/2) or not. If the given number n is a multiple of any integer between 2 and (n/2), then n will be not a prime number.

This method is similar to example 1, In which we are just reducing the number of iteration to optimize the code.

#include <stdio.h>

#define PRIME_NUMBER  1

int isPrimeNumber(int number)
{
    int iLoop = 0;
    int iPrimeFlag = 1;
    int iLimit = number/2;  //Divide the number by 2

    if(number <= 1)
    {
        iPrimeFlag = 0;
    }
    else
    {
        for(iLoop = 2; iLoop <= iLimit; iLoop++)
        {

            if((number % iLoop) == 0)  // Check prime number
            {
                iPrimeFlag = 0;
                break;
            }
        }

    }

    return iPrimeFlag;
}

int main()
{
    int retvalue = 0;
    int number = 0;

    printf("Enter the number : ");
    scanf("%d",&number);

    retvalue = isPrimeNumber(number);

    if (retvalue == PRIME_NUMBER)
    {
        printf("\n\n%d is prime number..\n\n", number);
    }
    else
    {
        printf("\n\n%d is not a prime number..\n\n", number);
    }
    return 0;
}

Output:

Prime number in c

 

 

 

prime number in c

 

 

Example 3:

There is another efficient way to find the prime number. In the below code to check prime number, we are checking that the given number n is a multiple of any integer between 2 and the square root of n. or not. If the given number n is a multiple of any integer between 2 and the square root of n., then n will be not a prime number.

#include <stdio.h>
#include <math.h>

#define PRIME_NUMBER  1

int isPrimeNumber(int number)
{
    int iLoop = 0;
    int iPrimeFlag = 1;
    int iLimit = sqrt(number); // calculate of square root n

    if(number <= 1)
    {
        iPrimeFlag = 0;
    }
    else
    {
        for(iLoop = 2; iLoop <= iLimit; iLoop++)
        {
            if((number % iLoop) == 0) // Check prime number
            {
                iPrimeFlag = 0;
                break;
            }
        }
    }
    return iPrimeFlag;
}

int main()
{
    int retvalue = 0;
    int number = 0;

    printf("Enter the number : ");
    scanf("%d",&number);

    retvalue = isPrimeNumber(number);

    if (retvalue == PRIME_NUMBER)
    {
        printf("\n\n%d is prime number..\n\n", number);
    }
    else
    {
        printf("\n\n%d is not a prime number..\n\n", number);
    }

    return 0;
}

Output:

prime number in c

prime number in c

 

 

 

 

 

Find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. First create a list of consecutive integers numbers from 2 to n: (2, 3, 4, …, n).
  2. Initially, let q equal 2, the smallest prime number.
  3. Find the all multiple of q by counting to n from 2q in increments of q, and mark them on the list. (these will be 2q, 3q, 4q, …; the q itself should not be marked).
  4. Find the first number greater than q in the list that is not marked. If there was no such number, stop. Otherwise, let q now equal this new number (which is the next prime), and repeat from step 3.

When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Algorithms of Sieve of Eratosthenes

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,

initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:

  if A[i] is true:

    for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :

      A[j] := false

 

Output: all i for which A[i] is true is the prime number.

Steps to find all the prime numbers less than or equal to 15 using the above mentioned algorithm, proceed as follows.

  • First, create an array of integers from 2 to 15 and initially mark all the elements as a prime number.
    2 3 4 5 6 7 8 9 10 11 12 13 14 15
  • The first prime number in the list is 2, marked every number in the list, which is multiple of 2.
    2 3 4 5 6 7 8 9 10 11 12 13 14 15
  • The next unmarked number in the list after 2 is 3, marked every number in the list, which is multiple of 3.
    2 3 4 5 6 7 8 9 10 11 12 13 14 15
  • The next number not yet marked out in the list after 3 is 5, but 5*5 is greater than 15. So here we will stop the process because all members have been marked out at this point.

Note: All unmarked numbers on the list are prime numbers.

C program to find all prime number up to n

 

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>


void GetRangeOfPrimeNumber(const int n, char *pcRangePrimeNum)
{
    int aIndex = 0;
    //Set pcRangePrimeNum 1 from  pcRangePrimeNum[0..n]
    memset(pcRangePrimeNum, 1,(n+1));
    pcRangePrimeNum[0] = 0;
    pcRangePrimeNum[1] = 0;
    int iLimit = sqrt(n);
    for (aIndex=2; aIndex <= iLimit; aIndex++)
    {
        // If pcRangePrimeNum[aIndex] is not changed, then it is a prime
        if (pcRangePrimeNum[aIndex] == 1)
        {
            int i;
            // Update all multiples of p
            for (i=aIndex*2; i<=n; i += aIndex)
            {
                pcRangePrimeNum[i] = 0;
            }
        }
    }
}
// Driver Program to test above function
int main()
{
    int n =0;
    int iPrimeNumber =0;
    char *pcPrimeNumber = NULL;
    printf("Enter the number: ");
    scanf("%d",&n);
    if(n <= 1)
    {
        printf("\n\nIt is not a prime number\n\n");
        return 0;
    }
    else
    {
        // Allocate memory for list
        pcPrimeNumber = malloc(sizeof(char)*(n+1));
        //Get the prime numbers
        GetRangeOfPrimeNumber(n,pcPrimeNumber);
        printf("\n\nThere are following prime numbers smaller than or equal to \n\n" );
        // Print all the prime numbers
        for (iPrimeNumber=2; iPrimeNumber<=n; iPrimeNumber++)
        {
            if (pcPrimeNumber[iPrimeNumber])
            {
                printf("prime %d\n",iPrimeNumber);
            }
        }
        free(pcPrimeNumber); // free the allocated memory
    }
    return 0;
}

Output:

prime number upto n

 

 

 

 

Recommended Articles for you:




References:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes