1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include <ccan/eratosthenes/eratosthenes.h>
3 #include <ccan/bitmap/bitmap.h>
8 #define VAL_TO_BIT(v) (((v) - 3) / 2)
9 #define LIMIT_TO_NBITS(l) ((l > 2) ? ((l) - 2) / 2 : 0)
11 #define BIT_TO_VAL(b) (((b) * 2) + 3)
13 void eratosthenes_init(struct eratosthenes *s)
19 void eratosthenes_reset(struct eratosthenes *s)
26 static void eratosthenes_once(struct eratosthenes *s, unsigned long limit, unsigned long p)
28 unsigned long n = VAL_TO_BIT(3*p);
29 unsigned long obits = LIMIT_TO_NBITS(s->limit);
32 n = obits + p - 1 - ((obits - n - 1) % p);
35 assert((BIT_TO_VAL(n) % p) == 0);
36 assert((BIT_TO_VAL(n) / p) > 1);
38 while (n < LIMIT_TO_NBITS(limit)) {
39 bitmap_clear_bit(s->b, n);
44 static void eratosthenes_sieve_(struct eratosthenes *s, unsigned long limit)
48 while ((p * p) < limit) {
51 eratosthenes_once(s, limit, p);
53 n = bitmap_ffs(s->b, VAL_TO_BIT(p) + 1, LIMIT_TO_NBITS(limit));
55 /* We should never run out of primes */
56 assert(n < LIMIT_TO_NBITS(limit));
62 void eratosthenes_sieve(struct eratosthenes *s, unsigned long limit)
64 if ((limit < 3) || (limit <= s->limit))
69 s->b = bitmap_alloc1(LIMIT_TO_NBITS(limit));
71 s->b = bitmap_realloc1(s->b, LIMIT_TO_NBITS(s->limit),
72 LIMIT_TO_NBITS(limit));
77 eratosthenes_sieve_(s, limit);
82 bool eratosthenes_isprime(const struct eratosthenes *s, unsigned long n)
94 return bitmap_test_bit(s->b, VAL_TO_BIT(n));
97 unsigned long eratosthenes_nextprime(const struct eratosthenes *s, unsigned long n)
101 if ((n + 1) >= s->limit)
110 i = bitmap_ffs(s->b, VAL_TO_BIT(n) + 1, LIMIT_TO_NBITS(s->limit));
111 if (i == LIMIT_TO_NBITS(s->limit))
112 /* Reached the end of the sieve */
115 return BIT_TO_VAL(i);