Loading...
Searching...
No Matches
iterator.h File Reference

primesieve_iterator allows to easily iterate over primes both forwards and backwards. More...

`#include <stdint.h>`
`#include <stddef.h>`
Include dependency graph for iterator.h:
This graph shows which files directly or indirectly include this file:

## Classes

struct | primesieve_iterator
| C prime iterator, please refer to iterator.h for more information. More...

## Macros

#define | IF_UNLIKELY_PRIMESIEVE(x) if (x)

## Functions

void | primesieve_init (primesieve_iterator *it)
| Initialize the primesieve iterator before first using it.
void | primesieve_free_iterator (primesieve_iterator *it)
| Free all memory.
void | primesieve_clear (primesieve_iterator *it)
| Reset the start number to 0 and free most memory.
void | primesieve_jump_to (primesieve_iterator *it, uint64_t start, uint64_t stop_hint)
| Reset the primesieve iterator to start.
void | primesieve_skipto (primesieve_iterator *it, uint64_t start, uint64_t stop_hint)
| Reset the primesieve iterator to start.
void | primesieve_generate_next_primes (primesieve_iterator *)
| Used internally by primesieve_next_prime().
void | primesieve_generate_prev_primes (primesieve_iterator *)
| Used internally by primesieve_prev_prime().
static uint64_t | primesieve_next_prime (primesieve_iterator *it)
| Get the next prime.
static uint64_t | primesieve_prev_prime (primesieve_iterator *it)
| Get the previous prime.

## 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 about PrimePi(n^0.5) * 8 bytes.

The primesieve_iterator.c example shows how to use primesieve_iterator. If any error occurs primesieve_next_prime() and primesieve_prev_prime() return PRIMESIEVE_ERROR. Furthermore primesieve_iterator.is_error is initialized to 0 and set to 1 if any error occurs.

Copyright (C) 2024 Kim Walisch, kim.w.nosp@m.alis.nosp@m.ch@gm.nosp@m.ail..nosp@m.com

This file is distributed under the BSD License. See the COPYING file in the top level directory.

## Function Documentation

## primesieve_clear()

void primesieve_clear | ( | primesieve_iterator * | it | ) |

Reset the start number to 0 and free most memory.

Keeps some smaller data structures in memory (e.g. the IteratorData object) that are useful if the primesieve_iterator is reused. The remaining memory uses at most 2 kilobytes.

## primesieve_generate_next_primes()

void primesieve_generate_next_primes | ( | primesieve_iterator * |  | ) |

Used internally by primesieve_next_prime().

primesieve_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 function also updates the i & size member variables of the primesieve_iterator struct. The size of the primes array varies, but it is > 0 and usually close to 2^10. If an error occurs primesieve_iterator.is_error is set to 1 and the primes array will contain PRIMESIEVE_ERROR.

## primesieve_generate_prev_primes()

void primesieve_generate_prev_primes | ( | primesieve_iterator * |  | ) |

Used internally by primesieve_prev_prime().

primesieve_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 function also updates the i & size member variables of the primesieve_iterator struct. The size of the primes array varies, but it is > 0 and ~ O(sqrt(n)). If an error occurs primesieve_iterator.is_error is set to 1 and the primes array will contain PRIMESIEVE_ERROR.

## primesieve_jump_to()

void primesieve_jump_to | ( | primesieve_iterator * | it,
|  | uint64_t | start,
|  | uint64_t | stop_hint
| ) |  |

Reset the primesieve iterator to start.

Parameters

  start | Generate primes >= start (or <= start).
  stop_hint | Stop number optimization hint. E.g. if you want to generate the primes <= 1000 use stop_hint = 1000, if you don't know use UINT64_MAX.

Examples
  prev_prime.c, and primesieve_iterator.c.

## primesieve_next_prime()

static uint64_t primesieve_next_prime | ( | primesieve_iterator * | it | ) |

inline static

Get the next prime.

Returns PRIMESIEVE_ERROR (UINT64_MAX) if any error occrus.

Examples
  primesieve_iterator.c.

## primesieve_prev_prime()

static uint64_t primesieve_prev_prime | ( | primesieve_iterator * | it | ) |

inline static

Get the previous prime.

primesieve_prev_prime(n) returns 0 for n <= 2. Note that primesieve_next_prime() runs up to 2x faster than primesieve_prev_prime(). Hence if the same algorithm can be written using either primesieve_prev_prime() or primesieve_next_prime() it is preferable to use primesieve_next_prime().

Examples
  prev_prime.c.

## primesieve_skipto()

void primesieve_skipto | ( | primesieve_iterator * | it,
|  | uint64_t | start,
|  | uint64_t | stop_hint
| ) |  |

Reset the primesieve iterator to start.

Parameters

  start | Generate primes > start (or < start).
  stop_hint | Stop number optimization hint. E.g. if you want to generate the primes <= 1000 use stop_hint = 1000, if you don't know use UINT64_MAX.