diff options
| author | Tyge Løvset <[email protected]> | 2020-07-30 12:50:56 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2020-07-30 12:50:56 +0200 |
| commit | 39d6f5ccd16360cd38d5d43752b4325aa6575bac (patch) | |
| tree | d3d785be4621e45b837d84e208ac7360f25ce814 /examples/prime.c | |
| parent | 3bf571bd7f0c8eface28bb5d2b7607d934865e00 (diff) | |
| download | STC-modified-39d6f5ccd16360cd38d5d43752b4325aa6575bac.tar.gz STC-modified-39d6f5ccd16360cd38d5d43752b4325aa6575bac.zip | |
Various cleanup of examples and READM.md. Added support for popcount on compilers without intrinsics.
Diffstat (limited to 'examples/prime.c')
| -rw-r--r-- | examples/prime.c | 47 |
1 files changed, 28 insertions, 19 deletions
diff --git a/examples/prime.c b/examples/prime.c index 2e6c99ee..974a7d90 100644 --- a/examples/prime.c +++ b/examples/prime.c @@ -1,35 +1,44 @@ #include <stdio.h>
#include <stc/cbitset.h>
+#include <stc/cvec.h>
-static inline void sieveOfEratosthenes(size_t n)
+declare_cvec(ux, uint64_t);
+
+static inline cvec_ux sieveOfEratosthenes(size_t n)
{
- cbitset_t prime = cbitset_make(n + 1, true);
- printf("computing prime numbers up to %zu\n", n);
- cbitset_reset(&prime, 0);
- cbitset_reset(&prime, 1);
+ cbitset_t pbits = cbitset_make(n + 1, true);
+ cbitset_reset(&pbits, 0);
+ cbitset_reset(&pbits, 1);
for (size_t i = 2; i <= n; ++i) {
- // If prime[i] is not changed, then it is a prime
- if (cbitset_test(prime, i) && i*i <= n) {
+ // If pbits[i] is not changed, then it is a prime
+ if (cbitset_test(pbits, i) && i*i <= n) {
for (size_t j = i*i; j <= n; j += i) {
- cbitset_reset(&prime, j);
+ cbitset_reset(&pbits, j);
}
}
}
+ puts("count:");
+ size_t np = cbitset_count(pbits);
puts("done");
- // Count the primes
- size_t count = 0;
- //for (size_t i = 1; i <= n; ++i)
- // if (cbitset_test(prime, i)) ++count;
- printf("number of primes: %zu\n", cbitset_count(prime));
- // print primes < 1000
- for (size_t i = 1; i <= 1000; ++i)
- if (cbitset_test(prime, i)) printf("%zu ", i);
- puts("");
- cbitset_destroy(&prime);
+ cvec_ux primes = cvec_init;
+ cvec_ux_reserve(&primes, np);
+ for (uint32_t i = 2; i <= n; ++i)
+ if (cbitset_test(pbits, i)) cvec_ux_push_back(&primes, i);
+
+ cbitset_destroy(&pbits);
+ return primes;
}
int main(void)
{
- sieveOfEratosthenes(1000000000);
+ int n = 1000000000;
+ printf("computing prime numbers up to %u\n", n);
+
+ cvec_ux primes = sieveOfEratosthenes(n);
+ printf("number of primes: %zu\n", cvec_size(primes));
+ for (size_t i = 0; i < 100; ++i)
+ printf("%zu ", primes.data[i]);
+
+ cvec_ux_destroy(&primes);
}
\ No newline at end of file |