From: Jimmy Kofler <koflerjim@...>
Date: 2007-03-02T23:05:44+09:00
Subject: C-ish bitwise prime sieve in Ruby?


Can we translate the following C-coded prime sieve by Frank Pilhofer
into a Ruby version that also uses bitwise operations?

Thanks for any suggestions!



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

/*
Sieve of Eratosthenes.
C code by Frank Pilhofer.
http://www.fpx.de/fp/Software/Sieve.html
*/


#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 *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  //printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                ++hits;
                //if  (++hits%2000L==0) {printf (" %ld. prime
number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld,
mom);
                }

  printf (" %ld prime numbers found in %ld secs.\n\nShow prime numbers",
          hits, time(NULL)-begin);

  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(feld,count)) printf ("%ld\t",
count);
        }
  free (feld);
  return 0;
}

-- 
Posted via http://www.ruby-forum.com/.