#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;
}

### Like this:

Like Loading...

*Related*