Seive1

seive1.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>

#define BLOCK 30
#define CHECK(X, Y) (X & (1 << (Y - 1)))

int main(int argc, char** argv) {
  uint32_t *p;
  uint64_t l, i, j, n;

  if(argc < 2) {
    fprintf(stderr, "Pass an argument\n");
    exit(EXIT_FAILURE);
  }

  l = strtoull(argv[1], NULL, 0);

  p = (uint32_t*)calloc((int)ceil(l), sizeof(uint32_t));

  fprintf(stderr, "\r\e[K2");
  memset(p, 0xaaaaaaaa | 0x24924924 | 0x21084210, (int)ceil(l));
  p[0] = 0xaaaaaaa8 | 0x24924920 | 0x21084200;

  for(i = 7; i < (int)ceil(sqrt(l * BLOCK)); ++i) {
    n = i / BLOCK;
    j = i % BLOCK;
    if(!CHECK(p[n], j)) {
      fprintf(stderr, "\r\e[K%llu", i);
      for(j = i * 2; j < l * BLOCK; j += i) {
        uint64_t t = j;
        if(j / BLOCK >= 1) {
          n = j / BLOCK;
          t = j % BLOCK;
        }
        p[n] |= 1 << (t - 1);
      }
    }
  }
  fprintf(stderr, "\r\e[K");

  if(argc > 2) {
    for(i = 2; i < l * BLOCK; ++i) {
      n = i / BLOCK;
      j = i % BLOCK;
      if(!CHECK(p[n], j)) {
        printf("%llu\n", i);
      }
    }
  }

  return 0;
}