Seive2

seive2.c

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

#define BLOCK 64

int main(int argc, char** argv) {
  uint64_t *prime, *mask, limit, i, j;

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

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

  prime = (uint64_t*)calloc(limit, sizeof(uint64_t));
  mask = (uint64_t*)calloc(ceil(sqrt(limit * BLOCK)), sizeof(uint64_t));

  for(i = 2; i < ceil(sqrt(limit * BLOCK)); ++i) {
    if(!(prime[i / BLOCK] & (1ULL << ((i % BLOCK) - 1)))) {
      fprintf(stderr, "\r\e[K%llu", i);
      for(j = 0; j < i; ++j) {
        mask[j] &= 0;
      }
      for(j = i * 2; j <= BLOCK * i; j += i) {
        mask[j / BLOCK] |= 1ULL << ((j % BLOCK) - 1);
      }
      for(j = 0; j < limit; ++j) {
        prime[j] |= mask[j % i];
      }
    }
  }

  fprintf(stderr, "\r\e[K");

  if(argc > 2) {
    for(i = 2; i < limit * BLOCK; ++i) {
      if(!(prime[i / BLOCK] & (1ULL << ((i % BLOCK) - 1)))) {
        printf("%llu\n", i);
      }
    }
  }

  free(prime);
  free(mask);

  return 0;
}