Loading...
Searching...
No Matches
SymEngine::Sieve Class Reference

Data Structures

class  iterator
 

Static Public Member Functions

static void generate_primes (std::vector< unsigned > &primes, unsigned limit)
 
static void clear ()
 
static void set_sieve_size (unsigned size)
 
static void set_clear (bool clear)
 

Static Private Member Functions

static void _extend (unsigned limit)
 

Static Private Attributes

static unsigned _sieve_size = 32 * 1024 * 8
 
static bool _clear = true
 

Detailed Description

Definition at line 18 of file prime_sieve.h.

Member Function Documentation

◆ _extend()

void SymEngine::Sieve::_extend ( unsigned  limit)
staticprivate

Definition at line 41 of file prime_sieve.cpp.

42{
43 std::vector<unsigned> &_primes = sieve_primes();
44#ifdef HAVE_SYMENGINE_PRIMESIEVE
45 if (_primes.back() < limit)
46 primesieve::generate_primes(_primes.back() + 1, limit, &_primes);
47#else
48 const unsigned sqrt_limit
49 = static_cast<unsigned>(std::floor(std::sqrt(limit)));
50 unsigned start = _primes.back() + 1;
51 if (limit <= start)
52 return;
53 if (sqrt_limit >= start) {
54 _extend(sqrt_limit);
55 start = _primes.back() + 1;
56 }
57
58 unsigned segment = _sieve_size;
59 std::valarray<bool> is_prime(segment);
60 for (; start <= limit; start += 2 * segment) {
61 unsigned finish = std::min(start + segment * 2 + 1, limit);
62 is_prime[std::slice(0, segment, 1)] = true;
63 // considering only odd integers. An odd number n corresponds to
64 // n-start/2 in the array.
65 for (unsigned index = 1; index < _primes.size()
66 and _primes[index] * _primes[index] <= finish;
67 ++index) {
68 unsigned n = _primes[index];
69 unsigned multiple = (start / n + 1) * n;
70 if (multiple % 2 == 0)
71 multiple += n;
72 if (multiple > finish)
73 continue;
74 std::slice sl = std::slice((multiple - start) / 2,
75 1 + (finish - multiple) / (2 * n), n);
76 // starting from n*n, all the odd multiples of n are marked not
77 // prime.
78 is_prime[sl] = false;
79 }
80 for (unsigned n = start + 1; n <= finish; n += 2) {
81 if (is_prime[(n - start) / 2])
82 _primes.push_back(n);
83 }
84 }
85#endif
86}
T back(T... args)
T floor(T... args)
T min(T... args)
T push_back(T... args)
T size(T... args)
T sqrt(T... args)

◆ clear()

void SymEngine::Sieve::clear ( )
static

Definition at line 26 of file prime_sieve.cpp.

27{
28 std::vector<unsigned> &_primes = sieve_primes();
29 _primes.erase(_primes.begin() + 10, _primes.end());
30}
T begin(T... args)
T end(T... args)
T erase(T... args)

◆ generate_primes()

void SymEngine::Sieve::generate_primes ( std::vector< unsigned > &  primes,
unsigned  limit 
)
static
Parameters
primesholds all primes up to the limit (including).

Definition at line 88 of file prime_sieve.cpp.

89{
90 _extend(limit);
91 std::vector<unsigned> &_primes = sieve_primes();
92 auto it = std::upper_bound(_primes.begin(), _primes.end(), limit);
93 // find the first position greater than limit and reserve space for the
94 // primes
95 primes.reserve(it - _primes.begin());
96 std::copy(_primes.begin(), it, std::back_inserter(primes));
97 if (_clear)
98 clear();
99}
T back_inserter(T... args)
T copy(T... args)
T reserve(T... args)
T upper_bound(T... args)

◆ set_clear()

void SymEngine::Sieve::set_clear ( bool  clear)
static

Definition at line 21 of file prime_sieve.cpp.

22{
23 _clear = clear;
24}

◆ set_sieve_size()

void SymEngine::Sieve::set_sieve_size ( unsigned  size)
static

Definition at line 32 of file prime_sieve.cpp.

33{
34#ifdef HAVE_SYMENGINE_PRIMESIEVE
35 primesieve::set_sieve_size(size);
36#else
37 _sieve_size = size * 1024 * 8; // size in bits
38#endif
39}

Field Documentation

◆ _clear

bool SymEngine::Sieve::_clear = true
staticprivate

Definition at line 24 of file prime_sieve.h.

◆ _sieve_size

unsigned SymEngine::Sieve::_sieve_size = 32 * 1024 * 8
staticprivate

Definition at line 23 of file prime_sieve.h.


The documentation for this class was generated from the following files: