Find prime numbers up to n using trial division and Sieve of Eratosthenes algorithm

Previously we have read how to find prime number using C code, here we will learn how to find the all prime number up to n.

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.

There are many ways to find all prime numbers up to n. In this blog post, we will discuss the Trial division method and the Sieve of Eratosthenes algorithm.

Let us see an example to understand the sentence “prime numbers up to n”.

Suppose a given number is n, the task is to print all prime numbers up to n. So if the user enters 10 then the output will be 2,3,5,7.

Trial Division Method

Example 1.

It is the simplest way to find the all prime numbers of an integer n. In this method, we are using two loops outer and nested. The outer loop is used to produce the numbers up to “n” and the nested loop is used to check the numbers for the prime number. If any of the numbers are prime then nested loop print this number.

#include<stdio.h>


int main(int argc, char *argv[])
{
    int iRetValue = 0;
    int iNumber = 0;
    int iLoop =0;
    int iLoopin =0;
    int iLimit =0;
    int iPrimeFlag = 0;


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


    if( iNumber <= 1)
    {
        printf("\n\nEnter a Valid number\n");

        return 0;
    }
    else
    {
        //outer loop to create the number
        for(iLoop=2 ; iLoop <= iNumber; iLoop++)
        {
            iPrimeFlag = 0; // Assign value to flag

            // Calculate the limit for nested loop
            iLimit = iLoop/2;

            for(iLoopin = 2; iLoopin <= iLimit; iLoopin++)
            {
                // Check prime number
                if((iLoop % iLoopin) == 0)
                {
                    iPrimeFlag = 1;
                    break;
                }
            }
            if(iPrimeFlag == 0) //Print if number is prime
            {
                printf("\n %d is a prime number..\n", iLoop);
            }
        }
    }

    return 0;
}

Output of the program

Example 2.

In this method, we are using a loop and function to find all prime numbers of an integer. The loop is used to create numbers up to n and function is used to check the number prime or not. If the number is a prime number then the function return “1” either its returns “0”.

#include <stdio.h>

#define PRIME_NUMBER  1

int IsPrimeNumber(int iNumber)
{
    int iLoop = 0;
    int iPrimeFlag = 1;

    //Divide the number by 2
    int iLimit = iNumber/2;


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

    return iPrimeFlag;
}



int main(int argc, char *argv[])
{

    int iRetValue = 0;
    int iNumber = 0;
    int iLoop =0;

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

    if( iNumber <= 1)
    {
        printf("\n\nEnter a Valid number\n");

        return 0;
    }
    else
    {
        for(iLoop=2 ; iLoop <= iNumber; iLoop++)
        {
            iRetValue = IsPrimeNumber(iLoop);

            //Check Prime Number
            if (iRetValue == PRIME_NUMBER)
            {
                printf("\n%d is prime number..\n", iLoop);
            }
        }
    }

    return 0;
}

Output of the above program

If you want to learn more about c language, here free trial c video course for you.

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

First create a list of consecutive integers numbers from 2 to n: (2, 3, 4, …, n).
Initially, let q equal 2, the smallest prime number.
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).
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

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.

Example:

To find all the prime numbers less than or equal to 15, 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 in 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 of the program: