#include <stdio.h>
#include <math.h>
int main(void){
long const topnumber = 62837329; // highest number to test for prime
long primetofind = 3700000; //nth prime we are looking for, BASE 1
unsigned char number_array[topnumber/8+1] // Our array of numbers, BASE 0
= {3,0}; // all initialized to 0's
// 0 and 1 are not primes
long i = 0, j = 0, k = 0;
for( i=2; i <= sqrt(topnumber); ++i)
if( !( number_array[i/8] & (1<<i%8) )
&& (++k)) // i IS A prime
{
// printf( " %d%s", i, !(k%20)?"\n":"");
for(j = i * i; j <= topnumber; j += i) // START FROM SQR(prime)
number_array[j/8] |= (1 << j%8); // NOT a prime
}
printf("\n %d primes needed to test primality upto %d", k, topnumber );
for(i=0, j=0, k=0; i <= topnumber; ++i) // j-th prime, 1-based (2 is 1st)
if( !( number_array[i/8] & (1<<(i%8)) )
&& (k=i)
&& ++j == primetofind )
printf("\n %dth prime is: %d\n", j, i);
printf("\n primes not bigger than %d: %d total", topnumber, j);
printf("\n the topmost prime found is %d.", k);
return 0;
}