Primes less than and up to N

This is a simple implementation of the Sieve of Eratosthenes algo

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

//a prime number is one which is divisible by 1 and itself only

//this program prints prime less than or upto N

int main(int argc,char* argv[]){
	char *nums;
	int limit=atoi(argv[1]);
	
	int l=(int)sqrt(limit);
	
	nums=calloc(limit,sizeof(char));
	int i;
	
        nums[0]=nums[1]=1;
	//nums[i]=0 its prime
	//else its not prime

        //the Algo used is Seive of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
        //Algorithmic complexity O(nloglogn)
        
	for(i=2;i<l;i++)
	{
		if(nums[i]==0)
		{
			int j;
			for(j=i+i;j<limit;j=j+i)
			{
				if(nums[j]==0)
					nums[j]=1;//basically if nums[i] is prime then all multiples of nums[i] are non prime
						  //this procedure need to be repeated for only the first sqrt(n) numbers
			}
		}
	}
	
	for(i=0;i<limit;i++)
	{
		if(nums[i]==0)
			printf("\n%d",i);
	}
	
	return 0;
}		
Advertisements

Let me know what you think

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s