primesieve 12.3
|
primesieve::iterator allows to easily iterate over primes both forwards and backwards. More...
#include <iterator.hpp>
Public Member Functions | |
iterator () noexcept | |
Create a new iterator object. | |
iterator (uint64_t start, uint64_t stop_hint=std::numeric_limits< uint64_t >::max()) noexcept | |
Create a new iterator object. | |
void | jump_to (uint64_t start, uint64_t stop_hint=std::numeric_limits< uint64_t >::max()) noexcept |
Reset the primesieve iterator to start. | |
iterator (const iterator &)=delete | |
primesieve::iterator objects cannot be copied. | |
iterator & | operator= (const iterator &)=delete |
iterator (iterator &&) noexcept | |
primesieve::iterator objects support move semantics. | |
iterator & | operator= (iterator &&) noexcept |
~iterator () | |
Frees all memory. | |
void | clear () noexcept |
Reset the start number to 0 and free most memory. | |
void | generate_next_primes () |
Used internally by next_prime(). | |
void | generate_prev_primes () |
Used internally by prev_prime(). | |
uint64_t | next_prime () |
Get the next prime. | |
uint64_t | prev_prime () |
Get the previous prime. | |
Public Attributes | |
std::size_t | i_ |
Current index of the primes array. | |
std::size_t | size_ |
Current number of primes in the primes array. | |
uint64_t | start_ |
Generate primes >= start. | |
uint64_t | stop_hint_ |
Generate primes <= stop_hint. | |
uint64_t * | primes_ |
The primes array. | |
void * | memory_ |
Pointer to internal IteratorData data structure. | |
primesieve::iterator allows to easily iterate over primes both forwards and backwards.
Generating the first prime has a complexity of O(r log log r) operations with r = n^0.5, after that any additional prime is generated in amortized O(log n log log n) operations. The memory usage is PrimePi(n^0.5) * 8 bytes.
|
noexcept |
Create a new iterator object.
Generate primes >= 0. The start number is default initialized to 0 and the stop_hint is default initialized UINT64_MAX.
|
noexcept |
Create a new iterator object.
start | Generate primes >= start (or <= start). |
stop_hint | Stop number optimization hint, gives significant speed up if few primes are generated. E.g. if you want to generate the primes <= 1000 use stop_hint = 1000. |
|
noexcept |
Reset the start number to 0 and free most memory.
Keeps some smaller data structures in memory (e.g. the PreSieve object) that are useful if the primesieve::iterator is reused. The remaining memory uses at most 200 kilobytes.
void primesieve::iterator::generate_next_primes | ( | ) |
Used internally by next_prime().
generate_next_primes() fills (overwrites) the primes array with the next few primes (~ 2^10) that are larger than the current largest prime in the primes array or with the primes >= start if the primes array is empty. Note that this method also updates the i & size member variables of this primesieve::iterator struct. The size of the primes array varies, but it is > 0 and usually close to 2^10.
void primesieve::iterator::generate_prev_primes | ( | ) |
Used internally by prev_prime().
generate_prev_primes() fills (overwrites) the primes array with the next few primes ~ O(sqrt(n)) that are smaller than the current smallest prime in the primes array or with the primes <= start if the primes array is empty. Note that this method also updates the i & size member variables of this primesieve::iterator struct. The size of the primes array varies, but it is > 0 and ~ O(sqrt(n)).
|
noexcept |
Reset the primesieve iterator to start.
start | Generate primes >= start (or <= start). |
stop_hint | Stop number optimization hint, gives significant speed up if few primes are generated. E.g. if you want to generate the primes <= 1000 use stop_hint = 1000. |
|
inline |
Get the next prime.
Throws a primesieve::primesieve_error exception (derived from std::runtime_error) if any error occurs.
|
inline |
Get the previous prime.
prev_prime(n) returns 0 for n <= 2. Note that next_prime() runs up to 2x faster than prev_prime(). Hence if the same algorithm can be written using either prev_prime() or next_prime() it is preferable to use next_prime().
uint64_t* primesieve::iterator::primes_ |
The primes array.
The current smallest prime can be accessed using primes[0]. The current largest prime can be accessed using primes[size-1].