links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

The sieve of eratosthenes

C++

// Written by Dane Kennedy
// It has the limitation of only being able to print out primes
// less than 100000000... Change absolute_max if you want more.
// It will gobble up your memory.
#include <iostream>
#include <cstdlib>

using namespace std;

#define absolute_max 100000000
static char bytes=sizeof(char);
static char bytes_shifted=bytes<<3;

unsigned long int which_byte;
unsigned long int which_bit;
unsigned long int next_byte;
char next_bit;
unsigned long int i_long_int;
unsigned long int j_long_int;

char primes[absolute_max/(sizeof(char)*8)]; // Change this if you change
                                            // absolute_max

unsigned char powertwo(char power) {
  unsigned char val=1;
  for (char i=0; i<power; i++)
    val<<=1;
  return val;
}

void create_primes(long int max, char* list) {
/* implements an Eratosthene's sieve. I have made the code as obscure
   as possible in the hopes that it will eek out some performance. Each
   bit in the array represents an integer. This is done so that
   efficient use of memory is made - both smaller and making fewer cache
   misses. Easy to make even smaller and faster by leaving out the evens...
*/
  static unsigned long int max_div_bits = max/(bytes_shifted);
  static unsigned long int max_div_two = max>>1;
  char bit_vals[bytes];

  for (char i=0;i<bytes_shifted;i++) {
    bit_vals[i]=~powertwo(i);
  }

  for (i_long_int=0; i_long_int<max_div_bits;i_long_int++) {
    list[i_long_int]=255;
  }

  for (i_long_int=2; i_long_int<max_div_two; i_long_int++) {
    which_byte=i_long_int/(bytes_shifted);
    which_bit=i_long_int%(bytes_shifted);
    if ((list[which_byte]>>(which_bit))&1) {
      for (j_long_int=i_long_int<<1; j_long_int<max; j_long_int+=i_long_int) {
        next_byte=j_long_int/(bytes_shifted);
        next_bit=j_long_int%(bytes_shifted);
        list[next_byte]&=bit_vals[next_bit];
      }
    }

  }
}

void echo_list(int max, char* list) {
  for (i_long_int=2; i_long_int<max; i_long_int++){
    which_byte=i_long_int/bytes_shifted;
    which_bit=i_long_int%bytes_shifted;
    if ((list[which_byte]>>(which_bit))&1) {
      cout << i_long_int << " ";
    }
  }
}

int main(int argc, char *argv[]) {
  unsigned long int max;
  
  // note: this line changed by dk
  // to allow for command line args
  max = strtol(argv[1], (char **)NULL, 10);
  // cin >> max;

  if (max>absolute_max)
    max=absolute_max;
  create_primes(max,primes);
  echo_list(max,primes);
  return 0;
}

back to Eratosthenes page

stats

It is Saturday May 17, 2008 10:56 am
This page served 1685 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:56:33 up 23 days, 11:38, 0 users, load average: 0.00, 0.00, 0.00