prime_generation Module Reference

Generate prime numbers. More...

Classes
class	ntlib::sieve_235< Allocator >

Functions
template<Integer T, typename SieveType, std::size_t SEGMENT_SIZE, bool CREATE_LIST>
SieveType	ntlib::eratosthenes_segmented (T N, std::vector< T > &primes)
	Generates a prime sieve.
template<Integer T, typename SieveType = ntlib::sieve_235<>, std::size_t SEGMENT_SIZE = (1 << 18)>
SieveType	ntlib::prime_sieve (T N)
	Generates a prime sieve.
template<Integer T, typename SieveType = ntlib::sieve_235<>, std::size_t SEGMENT_SIZE = (1 << 18)>
SieveType	ntlib::prime_sieve (T N, std::vector< T > &primes)
	Generates a prime sieve.
template<Integer T>
constexpr T	ntlib::next_prime (T n) noexcept
	Find the smallest prime bigger than a given number.

Detailed Description

Generate prime numbers.

A sieve of fixed capacity that stores all multiples of 2, 3 and 5 only implicitly.

There are function templates to genrate single prime numbers, lists of primes and prime sieves.

:sieve_235

All strict multiples of 2, 3 and 5 are always zero while 2, 3 and 5 however are always true.

This allows to optimize for space as from every 30 consecutive numbers only the eight ones with residues 1, 7, 11, 13, 17, 19, 23, 29 modulo 30 need to be stored explicitly. Those can be stored in a single byte resulting in a memory improvement by a factor of 30 compared to a std::vector<std::byte> or by a factor of 15/4 compared to a std::vector<bool>.

Files
file	modules/prime_generation/prime_generation.cpp
	Primary module interface unit for module prime_generation.
file	modules/prime_generation/sieve_235.cpp
	Module interface unit for module prime_generation, partition sieve_235.

---

Generated by  1.16.1