Sieve-of-Eratosthenes, Algorithm to find prime numbers up to an integer.

Sieve-of-Eratosthenes is a simple, efficient and fast algorithm for finding all prime numbers up to an integer number. This post explains Sieve-of-Eratosthenes algorithm, and its implementation in C language.

Algorithm & Flowchart

Input to Sieve-of-Eratosthenes algorithm is an integer number and output is all prime numbers which is less than the input number.

Sample Input : 10
Sample Output : 2, 3, 5, 7.

Algorithm

1. The algorithm takes a number as input. Assign this input to a variable ‘limit’
2. Assign variable i=2
3. Mark all numbers which is multiple of variable i and less than the ‘limit’.
4. Update value of i as the next unmarked number.
5. If variable i is greater than the ‘limit’, then stop. Else go to step 3.

The numbers that remains unmarked at the end of the algorithm are all prime numbers.Below figure shows the flow chart for the algorithm.

Implementation of Algorithm in C Language

Bit level programming reduces time and space complexity of the programs immensely. I have used some bit level programming in the following implementation of Sieve-of-Eratosthenes algorithm. Source code for the program can be downloaded from here

//Sieve of Eratosthenes algorithm to find prime numbers..
#include<stdio.h>
int main(int argc,char *argv[])
	{
	if(argc<2)
		printf("No argument passed.. \n");
	else 
		{
		//n is the upper limit of prime numbers
		//sample input : ./a.out 10
		//sample output: 2 3 5 7
		int n,i,k,j;
		n=atoi(argv[1]);
		int number_status[(n/32) +1];
		//number_status initialized to 0.
		for(i=0;i<=n/32;i++)
			number_status[i/32]=0;
		//i is initialized to first prime that is 2.
		i=2;
		for(;i<=n;i++)
			{
			//condition inside if becomes true, if i is a prime number. 
			//for example, if i=10, then number_status[10/32] & (1<<10) 
			//becomes zero. That means 10 th bit of number_status[0] is 0,
			//ie it is not marked.
			if(((number_status[i/32]) & (1<<i))==0)
				{
				//print i as prime number. and mark its corresponding 
				//multiples less than n.
				printf(" %d ", i);
				j=2*i;k=3;
				for(;j<=n;j=i*k,k++)
					number_status[j/32] |= 1<<j;
				}
			}
		printf(" \n");
		}
	}

This program takes the input from command line and assigns it to variable 'n'. The program should print all prime numbers less than n.

Variable i is initialized to 2, then numbers that are multiples of 2 and less than n are marked as not prime. Then program updates the value of variable i as next unmarked number, that is the next prime number. This procedure continues until variable i becomes greater than variable n.
A number can be in 2 states in this program, either marked as not prime or unmarked. Suppose if the limit is integer n, program should maintain status of n numbers. There is 2 ways to achieve this

Using array of n integers. That is

      int array[n];

//if i is prime, mark array[i*j]=1 where i*j<n



If we look at the space complexity of this program we find that, if n is the limit, then space complexity is n itself. Because program need n memory to store status of each 1 to n numbers. We can improve this using some bit level programming. 
Use one bit to represent a number's status. If number is marked, make  corresponding bit as 1.

Then an integer type variable which is 4 byte in size can be used to store status of 32 numbers. Space complexity then reduce greatly.


For example if limit is 100, then first method uses 100 integer data types, that is 400 bytes,  to store status. The second method uses 100/32 + 1 that is 4 integer data types, that is 16 bytes. 
I think this post helped you to understand Sieve-of-Eratosthenes algorithm and some advantages of bit level programming.Lastly i would like to say that i am not a regular blogger and this is my first blog post also, so pardon me if there is any mistake and feel free to comment.
		

About these ads