Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Functions
sieve.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

Go to the source code of this file.

Classes

struct  sieve

Defines

#define S_ISSET(S, B)   (((S)->bits[(B)/CHAR_BIT]>>((B)%CHAR_BIT))&1)
#define S_SET(S, B)   ((S)->bits[(B)/CHAR_BIT]|=(1<<((B)%CHAR_BIT)))
#define S_CLR(S, B)   ((S)->bits[(B)/CHAR_BIT]&=~(1<<((B)%CHAR_BIT)))
#define S_VAL(S, B)   ((S)->base+(2*(B)))
#define S_BIT(S, V)   (((V)-((S)->base))/2)

Typedefs

typedef unsigned char byte

Functions

void sieve_init (sieve *sp, long base, int nbits)
void sieve_grow (sieve *sp, int nbits)
long sieve_next (sieve *sp)
void sieve_reset (sieve *sp, long base)
void sieve_cross (sieve *sp, long val)
void sieve_clear (sieve *sp)
int main (int argc, char *argv[])

Class Documentation

struct sieve

Definition at line 66 of file sieve.c.

Collaboration diagram for sieve:
Class Members
long base
byte * bits
int nbits
int next
int size

Define Documentation

#define S_BIT (   S,
  V 
)    (((V)-((S)->base))/2)

Definition at line 85 of file sieve.c.

#define S_CLR (   S,
  B 
)    ((S)->bits[(B)/CHAR_BIT]&=~(1<<((B)%CHAR_BIT)))

Definition at line 83 of file sieve.c.

#define S_ISSET (   S,
  B 
)    (((S)->bits[(B)/CHAR_BIT]>>((B)%CHAR_BIT))&1)

Definition at line 81 of file sieve.c.

#define S_SET (   S,
  B 
)    ((S)->bits[(B)/CHAR_BIT]|=(1<<((B)%CHAR_BIT)))

Definition at line 82 of file sieve.c.

#define S_VAL (   S,
  B 
)    ((S)->base+(2*(B)))

Definition at line 84 of file sieve.c.


Typedef Documentation

typedef unsigned char byte

Definition at line 64 of file sieve.c.


Function Documentation

int main ( int  argc,
char *  argv[] 
)

Definition at line 87 of file sieve.c.

{
  sieve   s;
  long    pr, *p;
  int     c, ix, cur = 0;

  if(argc < 2) {
    fprintf(stderr, "Usage: %s <width>\n", argv[0]);
    return 1;
  }

  c = atoi(argv[1]);
  if(c < 0) c = -c;

  fprintf(stderr, "%s: sieving to %d positions\n", argv[0], c);

  sieve_init(&s, 3, c);

  c = 0;
  while((pr = sieve_next(&s)) > 0) {
    ++c;
  }

  p = calloc(c, sizeof(long));
  if(!p) {
    fprintf(stderr, "%s: out of memory after first half\n", argv[0]);
    sieve_clear(&s);
    exit(1);
  }

  fprintf(stderr, "%s: half done ... \n", argv[0]);

  for(ix = 0; ix < s.nbits; ix++) {
    if(S_ISSET(&s, ix)) {
      p[cur] = S_VAL(&s, ix);
      printf("%ld\n", p[cur]);
      ++cur;
    }
  }

  sieve_reset(&s, p[cur - 1]);
  fprintf(stderr, "%s: crossing off %d found primes ... \n", argv[0], cur);
  for(ix = 0; ix < cur; ix++) {
    sieve_cross(&s, p[ix]);
    if(!(ix % 1000))
      fputc('.', stderr);
  }
  fputc('\n', stderr);

  free(p);

  fprintf(stderr, "%s: sieving again from %ld ... \n", argv[0], p[cur - 1]);
  c = 0;
  while((pr = sieve_next(&s)) > 0) {
    ++c;
  }
  
  fprintf(stderr, "%s: done!\n", argv[0]);
  for(ix = 0; ix < s.nbits; ix++) {
    if(S_ISSET(&s, ix)) {
      printf("%ld\n", S_VAL(&s, ix));
    }
  }

  sieve_clear(&s);

  return 0;
}

Here is the call graph for this function:

void sieve_clear ( sieve sp)
void sieve_cross ( sieve sp,
long  val 
)
void sieve_grow ( sieve sp,
int  nbits 
)
void sieve_init ( sieve sp,
long  base,
int  nbits 
)
long sieve_next ( sieve sp)
void sieve_reset ( sieve sp,
long  base 
)