nsz Git - libfirm/blob - ir/be/test/langshootout/nsieve-bits.c

   1 /*
   2  * The Great Computer Language Shootout
   3  * http://shootout.alioth.debian.org/
   4  *
   5  * Written by Dima Dorfman, 2004
   6  * Compile: gcc -std=c99 -O2 -o nsieve_bits_gcc nsieve_bits.c
   7  */
   8
   9 #include <limits.h>
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <stdint.h>
  13 #include <string.h>
  14
  15 typedef uint_fast8_t bits;
  16 #define NBITS   (CHAR_BIT * sizeof(bits))
  17
  18 static uintmax_t
  19 nsieve(uintmax_t m)
  20 {
  21         uintmax_t count, i, j;
  22         bits a[m / NBITS];
  23
  24         memset(a, (1 << CHAR_BIT) - 1, sizeof(a));
  25         count = 0;
  26         for (i = 2; i < m; ++i)
  27                 if (a[i / NBITS] & (1 << i % NBITS)) {
  28                         for (j = i + i; j < m; j += i)
  29                                 a[j / NBITS] &= ~(1 << j % NBITS);
  30                         ++count;
  31                 }
  32         return (count);
  33 }
  34
  35 static void
  36 test(unsigned long n)
  37 {
  38         uintmax_t count, m;
  39
  40         m = (1 << n) * 10000;
  41         count = nsieve(m);
  42         printf("Primes up to %8ju %8ju\n", m, count);
  43 }
  44
  45 int
  46 main(int ac, char **av)
  47 {
  48         unsigned long n;
  49         char *cp;
  50
  51         if (ac < 2) {
  52 usage:          fprintf(stderr, "usage: nsieve N\n");
  53                 exit(2);
  54         }
  55         n = strtoul(av[1], &cp, 10);
  56         if (*av[1] == '\0' || *cp != '\0' || n == ULONG_MAX)
  57                 goto usage;
  58         test(n);
  59         if (n >= 1)
  60                 test(n - 1);
  61         if (n >= 2)
  62                 test(n - 2);
  63         exit(0);
  64 }