The first N primes

#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 the first N primes

int main(int argc,char* argv[]){
	char *nums;
	int n=atoi(argv[1]);
	
	int limit=n*log(n)+n*log(log(n));
	
	int count=0;
	/*
	* According to Rosser's Theorem the nth prime lies between
	* nln(n) and nln(n)+nln(ln(n))
	* http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
	*/
	
	
	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 && count<n;i++)
	{
		if(nums[i]==0)
		{       
		        count++;
			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
			}
		}
	}
	count =0;
	
	for(i=0;i<limit && count<n;i++)
	{
		if(nums[i]==0)
		{
			printf("\n%d",i);
			count++;
	        }
	}
	
	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