[ create a new paste ] login | about

Link: http://codepad.org/yAkF5X9C    [ raw code | output | fork ]

WillNess - C, pasted on Oct 27:
#include <stdio.h>
#include <math.h>

int main(void){

    long const topnumber = 22015177; // highest number to test for prime
    long primetofind = 1300000; //nth prime we are looking for, BASE 1
    unsigned char number_array[topnumber+1]  // Our array of numbers, BASE 0
                                           = {1,1,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] && (++k))            // i IS A prime
        for(j = i * i; j <= topnumber; j += i)  // START FROM SQR(prime)
            number_array[j] = 1;    // 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] && (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;
}


Output:
1
2
3
4
5
6

 634 primes needed to test primality upto 22015177
 1300000th prime is: 20495843

 primes not bigger than 22015177: 1390161 total
 the topmost prime found is 22015157.


Create a new paste based on this one


Comments: