# C-ish bitwise prime sieve in Ruby?

**URL:** <https://www.ruby-forum.com/t/c-ish-bitwise-prime-sieve-in-ruby/87426>\
**Category:** Ruby\
**Created:** [March 2, 2007, 3:05pm UTC](https://www.ruby-forum.com/t/c-ish-bitwise-prime-sieve-in-ruby/87426 "2007-03-02T15:05:42Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![jkit](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/f1d935/32.png) [@jkit](https://www.ruby-forum.com/u/jkit)\
**Post date:** [March 2, 2007, 3:05pm UTC](https://www.ruby-forum.com/t/c-ish-bitwise-prime-sieve-in-ruby/87426/1 "2007-03-02T15:05:42Z")

</div>

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](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;  
}

---

<div class="post-metadata">

**Author:** ![jkit](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/f1d935/32.png) [@jkit](https://www.ruby-forum.com/u/jkit)\
**Post date:** [March 2, 2007, 3:45pm UTC](https://www.ruby-forum.com/t/c-ish-bitwise-prime-sieve-in-ruby/87426/2 "2007-03-02T15:45:31Z")

</div>

On Mar 2, 7:05 am, Jimmy K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

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

Yes! Ruby supports bitwise operations on Integers. One thing to watch  
out for: Ruby’s integers are unbounded in size, so shifting left may  
produce different results in a Ruby Integer than on a 32- or 64-bit  
int in C. You’ll need to mask the values whenever something might  
overflow.

For example:

irb(main):001:0\> i = 0x7FFF\_FFFF  
=\> 2147483647  
irb(main):002:0\> ‘%032b’ % i  
=\> “01111111111111111111111111111111”  
irb(main):003:0\> i2 = i \<\< 1  
=\> 4294967294  
irb(main):004:0\> ‘%032b’ % i2  
=\> “11111111111111111111111111111110”  
irb(main):005:0\> i4 = i \<\< 2  
=\> 8589934588  
irb(main):006:0\> ‘%032b’ % i4  
=\> “111111111111111111111111111111100”  
irb(main):007:0\> i4 = (i \<\< 2) && 0xFFFF\_FFFF  
=\> 4294967295  
irb(main):008:0\> ‘%032b’ % i4  
=\> “11111111111111111111111111111111”

---

<div class="post-metadata">

**Author:** ![jkit](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/f1d935/32.png) [@jkit](https://www.ruby-forum.com/u/jkit)\
**Post date:** [March 2, 2007, 4:15pm UTC](https://www.ruby-forum.com/t/c-ish-bitwise-prime-sieve-in-ruby/87426/3 "2007-03-02T16:15:34Z")

</div>

On Mar 2, 7:05 am, Jimmy K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> /\*  
> Sieve of Eratosthenes.  
> C code by Frank Pilhofer.[The Sieve of Erastothenes](http://www.fpx.de/fp/Software/Sieve.html)  
> \*/

Also:  
a) [Eratosthenes ruby - Google Search](http://www.google.com/search?q=Eratosthenes+ruby)

b) If you’re doing this to learn Ruby, that’s fine. However, if you  
want speed, you might want to look at RubyInline, which lets you re-  
use pieces of C-code directly within Ruby.