Re: Sieve of Eratosthenes with closures

[Anonymous Monk]

Of course if you want fast, say 1 million primes in a second you would never use Perl. Perl is great for high level stuff. For raw algorithms.....

#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define TEST(f,x)    (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define SET(f,x)    *(f+(x)/16)|=1<<(((x)%16L)/2)

int
main(int argc, char *argv[])
{
    unsigned char *ptr=NULL;
    unsigned long max, mom, s=0, e=1;
    register unsigned long test=1;
    register unsigned long count=1;
    time_t begin;
    
    max = ( argc>1 ) ? atol(argv[1]) : 0xFFFFFFL;
    ptr = (unsigned char *) calloc( ((max>>4)+1L), sizeof(char) );
    if ( ! ptr ) {
        printf( "Can't allocate enough memory!\n" );
        system("pause");
      return 1;
    }

    printf( "Searching prime numbers to : %ld\n", max );
    
    begin = time (NULL);
    while ( (test+=2) < max) if (!TEST(ptr, test) ) {
        if  ( ++count%0xFFL==0 ) {
            printf ( "%ld prime number\x0d", count );
            fflush(stdout);
        }
        for ( mom=3L*test; mom<max; mom+=test<<1 ) SET (ptr, mom);
    }

    printf( " %ld prime numbers found in %ld secs.\n\n", count, time(N
+ULL)-begin);

    printf( "Show prime numbers ( Enter end < start to exit )" );
    while ( s<e ) {
        printf ("\n\nStart of Area : "); 
        fflush (stdout); scanf ("%ld", &s);
        printf ("End of Area   : ");     
        fflush (stdout); scanf ("%ld", &e);
        count = s-2;
        if ( s%2==0 ) count++;
        while ((count+=2)<e) if (!TEST(ptr,count)) printf ("%ld\t", co
+unt);
    }

    free(ptr);
  return 0;
}

/*

Searching prime numbers to : 16777215
 1077871 prime numbers found in 1 secs.

Show prime numbers ( Enter end < start to exit )

Start of Area : 1
End of Area   : 1000
1       3       5       7       11      13      17      19      23    
+  29
31      37      41      43      47      53      59      61      67    
+  71
73      79      83      89      97      101     103     107     109   
+  113
127     131     137     139     149     151     157     163     167   
+  173
179     181     191     193     197     199     211     223     227   
+  229
233     239     241     251     257     263     269     271     277   
+  281
283     293     307     311     313     317     331     337     347   
+  349
353     359     367     373     379     383     389     397     401   
+  409
419     421     431     433     439     443     449     457     461   
+  463
467     479     487     491     499     503     509     521     523   
+  541
547     557     563     569     571     577     587     593     599   
+  601
607     613     617     619     631     641     643     647     653   
+  659
661     673     677     683     691     701     709     719     727   
+  733
739     743     751     757     761     769     773     787     797   
+  809
811     821     823     827     829     839     853     857     859   
+  863
877     881     883     887     907     911     919     929     937   
+  941
947     953     967     971     977     983     991     997

Start of Area :

*/