Loading...
Searching...
No Matches
prime_sieve.h
1#ifndef SYMENGINE_PRIME_SIEVE_H
2#define SYMENGINE_PRIME_SIEVE_H
3
4#include <vector>
5
6// Sieve class stores all the primes upto a limit. When a prime or a list of
7// prime
8// is requested, if the prime is not there in the sieve, it is extended to hold
9// that
10// prime. The implementation is a very basic Eratosthenes sieve, but the code
11// should
12// be quite optimized. For limit=1e8, it is about 20x slower than the
13// `primesieve` library (1206ms vs 55.63ms).
14
15namespace SymEngine
16{
17
18class Sieve
19{
20
21private:
22 static void _extend(unsigned limit);
23 static unsigned _sieve_size;
24 static bool _clear;
25
26public:
27 // Returns all primes up to the `limit` (including). The vector `primes`
28 // should
29 // be empty on input and it will be filled with the primes.
31 static void generate_primes(std::vector<unsigned> &primes, unsigned limit);
32 // Clear the array of primes stored
33 static void clear();
34 // Set the sieve size in kilobytes. Set it to L1d cache size for best
35 // performance.
36 // Default value is 32.
37 static void set_sieve_size(unsigned size);
38 // Set whether the sieve is cleared after the sieve is extended in internal
39 // functions
40 static void set_clear(bool clear);
41
43 {
44
45 private:
46 unsigned _index;
47 unsigned _limit;
48
49 public:
50 // Iterator that generates primes upto limit
51 iterator(unsigned limit);
52 // Iterator that generates primes with no limit.
53 iterator();
54 // Destructor
55 ~iterator();
56 // Next prime
57 unsigned next_prime();
58 };
59};
60
61}; // namespace SymEngine
62
63#endif
static void generate_primes(std::vector< unsigned > &primes, unsigned limit)
Definition: prime_sieve.cpp:88
Main namespace for SymEngine package.
Definition: add.cpp:19