[−][src]Struct primal::StreamingSieve
A heavily optimised prime sieve.
This is a streaming segmented sieve, meaning it sieves numbers in
intervals, extracting whatever it needs and discarding it. See
Sieve
for a wrapper that caches the information to allow for
repeated queries, at the cost of O(limit) memory use.
This uses O(sqrt(limit)) memory, and is designed to be as
cache-friendly as possible. StreamingSieve
should be used for
one-off calls, or simple linear iteration.
The design is heavily inspired/adopted from Kim Walisch's primesieve, and has similar speed (around 5-20% slower).
Examples
let count = primal::StreamingSieve::prime_pi(123456); println!("𝜋(123456) = {}", count);
Implementations
impl StreamingSieve
[src]
pub fn prime_pi(n: usize) -> usize
[src]
Count the number of primes upto and including n
, that is, 𝜋,
the prime counting
function.
Examples
assert_eq!(primal::StreamingSieve::prime_pi(10), 4); // the endpoint is included assert_eq!(primal::StreamingSieve::prime_pi(11), 5); assert_eq!(primal::StreamingSieve::prime_pi(100), 25); assert_eq!(primal::StreamingSieve::prime_pi(1000), 168);
pub fn nth_prime(n: usize) -> usize
[src]
Trait Implementations
Auto Trait Implementations
impl RefUnwindSafe for StreamingSieve
impl Send for StreamingSieve
impl Sync for StreamingSieve
impl Unpin for StreamingSieve
impl UnwindSafe for StreamingSieve
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,