Fixed bugs in cbits. (bits_count() and is_disjoint()). Renamed is_disjoined() to disjoined() and cbits_subset() to cbits_subset_of().

Impoved prime.c sieveOfEratosthenes() now 2.5x faster.

1 files changed, 26 insertions, 21 deletions

diff --git a/examples/prime.c b/examples/prime.c
index 5c5d3969..f11f1627 100644
--- a/examples/prime.c
+++ b/examples/prime.c
@@ -1,39 +1,44 @@
 #include <stdio.h>

+#include <math.h>

+#include <time.h>

 #include <stc/cbits.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_pattern(n, 0xAAAAAAAAAAAAAAAA);

+    size_t q = sqrt(n);

+    cbits_reset(&bits, 1);

+    cbits_set(&bits, 2);

+

+    for (size_t j, i = 3; i <= q; i += 2) {

+        for (j = i; j < n; j += 2) {

+            if (cbits_test(bits, j)) {

+                i = j;

+                break;

             }

         }

+        for (j = i*i; j < n; j += i*2)

+            cbits_reset(&bits, j);

     }

-    return primes;

-} 

+    return bits;

+}

 

 

 int main(void)

 {

-    int n = 100000000;

+    size_t n = 100000000;

     printf("computing prime numbers up to %u\n", n);

-    

-    cbits primes = sieveOfEratosthenes(n);

-    puts("done");

-    

+

+    clock_t t1 = clock();

+    cbits primes = sieveOfEratosthenes(n + 1);

     size_t np = cbits_count(primes);

-    printf("number of primes: %zu\n", np);

+    clock_t t2 = clock();

+

+    printf("number of primes: %zu, time: %f\n", np, (t2 - t1)/(float)CLOCKS_PER_SEC);

 

-    printf("2 ");

-    c_forrange (i, int, 3, 1001, 2) {

+    for (size_t i=0; i<=1000; ++i)

        if (cbits_test(primes, i)) printf("%d ", i);

-    }

     puts("");

+

     cbits_del(&primes);

 }
\ No newline at end of file