primesieve 11.2
Loading...
Searching...
No Matches
Public Member Functions | Public Attributes | List of all members
primesieve::iterator Struct Reference

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.
 
iteratoroperator= (const iterator &)=delete
 
 iterator (iterator &&) noexcept
 primesieve::iterator objects support move semantics.
 
iteratoroperator= (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.
 

Detailed Description

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.

Examples
prev_prime.cpp, and primesieve_iterator.cpp.

Constructor & Destructor Documentation

◆ iterator() [1/2]

primesieve::iterator::iterator ( )
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.

◆ iterator() [2/2]

primesieve::iterator::iterator ( uint64_t  start,
uint64_t  stop_hint = std::numeric_limits< uint64_t >::max() 
)
noexcept

Create a new iterator object.

Parameters
startGenerate primes >= start (or <= start).
stop_hintStop 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.

Member Function Documentation

◆ clear()

void primesieve::iterator::clear ( )
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.

◆ generate_next_primes()

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.

◆ generate_prev_primes()

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)).

◆ jump_to()

void primesieve::iterator::jump_to ( uint64_t  start,
uint64_t  stop_hint = std::numeric_limits< uint64_t >::max() 
)
noexcept

Reset the primesieve iterator to start.

Parameters
startGenerate primes >= start (or <= start).
stop_hintStop 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.
Examples
prev_prime.cpp.

◆ next_prime()

uint64_t primesieve::iterator::next_prime ( )
inline

Get the next prime.

Throws a primesieve::primesieve_error exception (derived from std::runtime_error) if any error occurs.

Examples
primesieve_iterator.cpp.

◆ prev_prime()

uint64_t primesieve::iterator::prev_prime ( )
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().

Examples
prev_prime.cpp.

Member Data Documentation

◆ primes_

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].


The documentation for this struct was generated from the following file: