Another minor fix in cbits.h. Improved cbits_api.md example.

1 files changed, 25 insertions, 21 deletions

diff --git a/docs/cbits_api.md b/docs/cbits_api.md
index e4b60da6..006ce52a 100644
--- a/docs/cbits_api.md
+++ b/docs/cbits_api.md
@@ -64,40 +64,44 @@ void             cbits_xor(cbits *self, cbits other);        // set of disjoint
 ```c
 #include <stc/cbits.h>
 #include <stdio.h>
+#include <math.h>
+#include <time.h>
 
-static inline cbits sieveOfEratosthenes(size_t n)
+cbits sieveOfEratosthenes(size_t n)
 {
-    cbits primes = cbits_with_size(n + 1, true);
-    cbits_reset(&primes, 0);
-    cbits_reset(&primes, 1);
-
-    c_forrange (i, size_t, 2, n+1) {
-        // If primes[i] is not changed, then it is a prime
-        if (cbits_test(primes, i) && i*i <= n) {
-            c_forrange (j, size_t, i*i, n+1, i) {
-                cbits_reset(&primes, j);
+    cbits bits = cbits_with_size(n>>1, true);
+    size_t q = (size_t) sqrt(n);
+
+    for (size_t i = 3; i <= q; i += 2) {
+        for (size_t j = i; j < n; j += 2) {
+            if (cbits_test(bits, j>>1)) {
+                i = j;
+                break;
             }
         }
+        for (size_t j = i*i; j < n; j += i*2)
+            cbits_reset(&bits, j>>1);
     }
-    return primes;
+    return bits;
 }
 
 int main(void)
 {
-    int n = 100000000;
-    printf("computing prime numbers up to %u\n", n);
+    size_t n = 100000000;
+    printf("computing prime numbers up to %zu\n", n);
 
-    cbits primes = sieveOfEratosthenes(n);
-    puts("done");
+    clock_t t1 = clock();
+    cbits primes = sieveOfEratosthenes(n + 1);
+    size_t nprimes = cbits_count(primes);
+    clock_t t2 = clock();
 
-    size_t np = cbits_count(primes);
-    printf("number of primes: %zu\n", np);
+    printf("number of primes: %zu, time: %f\n", nprimes, (float)(t2 - t1)/CLOCKS_PER_SEC);
 
-    printf("2 ");
-    c_forrange (i, int, 3, 1001, 2) {
-       if (cbits_test(primes, i)) printf("%d ", i);
-    }
+    printf(" 2");
+    for (size_t i = 3; i < 1000; i += 2)
+       if (cbits_test(primes, i>>1)) printf(" %zu", i);
     puts("");
+
     cbits_del(&primes);
 }
 ```