/* calcprime - Calculates all the prime numbers up to a compiled-in limit using an Eratosthenes sieve

   By James Stanley

   No license - Use as you wish */

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

/*
//Use this to get the most out of the program
#define LIMIT 8589934591ULL
#define SQRTLIMIT 92682
#define LONG long long
#define FORMAT "%llu\n"
*/

/*
//Use this to check speed, needs 63MB of RAM
//NOTE: Currently 26s
#define LIMIT 1000000000
#define SQRTLIMIT 31623
#define LONG long
#define FORMAT "%lu\n"
*/


//Use this for checking accuracy
#define LIMIT 100
#define SQRTLIMIT 10
#define LONG long
#define FORMAT "%lu\n"


#define MEM_SIZE (LIMIT >> 4)+1

#define IS_PRIME(x) (sieve[x >> 4] & biton[(x >> 1) & 7])
#define SET_NOTPRIME(x) sieve[x >> 4] &= bitoff[(x >> 1) & 7]

unsigned char biton[8]  = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
unsigned char bitoff[8] = { 0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f };

int main() {
  unsigned char *sieve;
  unsigned LONG i, j;
  unsigned LONG i2;
  unsigned LONG is;
  
  //fprintf(stderr, "%d\n", (int)clock());
  
  sieve = malloc(MEM_SIZE);
  for(i = 0; i < MEM_SIZE; i++) {
    sieve[i] = 0xff;
  }
  
  //fprintf(stderr, "%d\n", (int)clock());
  
  for(i = 3; i < SQRTLIMIT; i += 2) {
    if(IS_PRIME(i)) {//Only mark off multiples of primes
      i2 = i*2;
      is = i*i;//We start off marking at it's square
      for(j = is; (j < LIMIT) && (j >= is); j += i2) {
        if(IS_PRIME(j)) SET_NOTPRIME(j);
      }
    }
  }
  
  //fprintf(stderr, "%d\n", (int)clock());
  
  SET_NOTPRIME(0);
  SET_NOTPRIME(1);

  
  printf("2\n");
  for(i = 1; i < LIMIT; i += 2) {
    if(IS_PRIME(i)) printf(FORMAT, i);
  }
  
  
  //fprintf(stderr, "%d\n", (int)clock());
  
  return 0;
}