prime_sieve package¶
Submodules¶
prime_sieve.array module¶
- class prime_sieve.array.PrimeArraySieve(dtype=<class 'numpy.uint64'>)[source]¶
Bases:
SegmentedPrimeSieveA numpy array implementation of a segmented prime sieve. It is relatively fast, but subject to possible overflow if you are working with very many primes.
- property primes¶
A read-only view of the currently computed primes. Do not modify the return value, make a copy first if needed.
- Returns
A sequence-like object of primes
prime_sieve.base module¶
- class prime_sieve.base.SegmentedPrimeSieve[source]¶
Bases:
ABCAn abstract segmented prime sieve. It can compute primes in chunks (segments) and return the so-far-computed primes at any time, or do prime finding or counting related operations. The values of the primes are stored for the duration of the object, so multiple computations potentially requiring further primes to be computed will be accelerated if the object is kept alive. The stored primes are guaranteed to be all the primes in the range [2, p_k^2) for some k, referred to as the end segment index.
- count_primes_in_range(n: int, m: int) int[source]¶
Count the number of primes in range(n, m), i.e. the number of primes p with n <= p < m. Primes are computed as necessary.
- Parameters
n – The lower bound.
m – The upper bound.
- Returns
The number of primes p with n <= p < m.
- count_primes_less_or_equal(n: int) int[source]¶
Count the number of primes less than or equal to a given bound. Primes are computed as necessary.
- Parameters
n – An integer.
- Returns
The number of primes less than or equal to n., commonly referred to as pi(n).
- ensure_len_greater_or_equal(n: int) None[source]¶
Precompute primes until at least n primes have been computed. Afterwards, it is guaranteed than the length of self is at least n. Most likely this will cause more than n primes to be computed.
- Parameters
n – The number of primes to ensure are computed.
- Returns
None
- ensure_max_greater_or_equal(n: int) None[source]¶
Precompute primes until the largest computed prime is at least n. Afterwards, it is guaranteed that that self.primes[-1] >= n. Most likely, afterwards self.primes[-1] > n even if n is prime.
- Parameters
n – An integer.
- Returns
None
- find_primes_until(stop_cb, progress_cb=None) None[source]¶
Compute more and more primes until a told to stop by the stop callback.
- Parameters
stop_cb – A callable accepting this object as its only argument whose return value’s truthiness indicates whether to stop computing.
progress_cb – A callable accepting this object as its only argument that will be called for each segment of primes computed.
- Returns
None
- index_of(p: int) int[source]¶
Return the index i of a prime p such that p = p_i.
- Returns
The index i such that p = p_i
- index_of_next_prime_greater_than(n: int) int[source]¶
Return the index i of the smallest prime p_i with p_i > n. Primes are computed as necessary.
- Parameters
n – An integer.
- Returns
the index i for which p_i is the smallest prime with p_i > n.
- index_of_prev_prime_less_than(n: int) int[source]¶
Return the index i of the largest prime p_i with p_i < n. Primes are computed as necessary.
- Parameters
n – An integer.
- Returns
the index i for which p_i is the largest prime with p_i < n.
- is_prime(n: int)[source]¶
Returns whether n is prime, computing new primes as necessary in order to check. Note: a sieve is not meant to be a primality checker, there are much faster ways to check primality than using a sieve.
- Parameters
n – An int to check whether it is prime.
- Returns
Whether n is prime.
- iter_all_primes()[source]¶
Yield all prime numbers starting at 2. The primes are computed as needed.
- Return A generator yielding all primes
- next_prime_greater_than(n: int)[source]¶
Return the smallest prime strictly greater than a given number. Primes are computed as necessary.
- Parameters
n – An integer.
- Returns
The smallest prime p with p > n.
- nth_prime(n: int)[source]¶
Returns the nth prime number, starting with p_0 = 2, p_1 = 3, etc. Primes are computed as necessary.
- Parameters
n – The zero-based index of the prime to compute.
- Returns
The nth prime number.
- prev_prime_less_than(n: int)[source]¶
Return the largest prime strictly less than a given number. Primes are computed as necessary.
- Parameters
n – An integer.
- Returns
The largest prime p with p < n.
- abstract property primes¶
A read-only view of the currently computed primes. Do not modify the return value, make a copy first if needed.
- Returns
A sequence-like object of primes
- primes_in_range(n: int, m: int)[source]¶
Returns a read-only view of primes in range(n,m), i.e. primes p with n <= p < m. Primes are computed as necessary. Do not modify the contents of the returned range, make a copy if necessary.
- Parameters
n – The lower bound (inclusive) of primes to compute.
m – The upper bound (exclusive) of primes to compute.
- Returns
A read-only sequence of prime p with n <= p < m.
prime_sieve.list module¶
- class prime_sieve.list.PrimeListSieve[source]¶
Bases:
SegmentedPrimeSieveA pure Python implementation of a segmented prime sieve. It is much slower than the numpy implementation, but has no dependencies and no possibility of overflow.
- property primes¶
A read-only view of the currently computed primes. Do not modify the return value, make a copy first if needed.
- Returns
A sequence-like object of primes
prime_sieve.math_utils module¶
Module contents¶
Top-level package for Prime Sieve.