Tools for generating filters and collections with primes concurrently.
Rust implementation of the Sieve of Atkin.
This implementation runs in O( sqrt(maxnum) + sectionsize ) with O( sectionsize ) memory. (where sectionsize = maxnum - minnum)
This implementation built to work well with parallel processing, distributed computing tasks, or if a reasonably large section of primes is desired within a range that is roughly quadratic to the size of the section. (e.g., If you need primes in a block of size 10^9 starting at roughtly 10^18.) By integrating Huon Wilson's primal package (see below), this package also is able to more quickly calculate all primes below a desired threshold through concurrency.
With this algorithm, there is no need to calculate smaller primes or to have any communication between threads, as each section of primes is calculated completely independently. Therefore, it is efficient for and very easily implemented in a distributed system.
This package takes advantage of the (very good) primal package by Huon Wilson (located here: https://crates.io/crates/primal) to compute the edge case with primes starting from 0. This is simply faster than using just the algorithm here, which is built for concurrency. The algorithm implemented there is approximately 12 times faster when calculating primes from 0 than this implementation. This package uses that to cut the time to find the same number of primes by 12/(cores+11).
concurrent_prime_sieve::filterRust
fn prime_filter(max_num: usize) -> Vec<bool>
Generates a vector of bools of size max_num, with
trueat each prime index, andfalseotherwise.The number of threads is based on the number of virtual cores detected.
Rust
fn prime_filter_concurrently(max_num: usize, threads: usize) -> Vec<bool>
Similar to
fn prime_filter, but allows for a custom number of threads.
Rust
fn prime_filter_sequentially(max_num: usize) -> Vec<bool>
Similar to
fn prime_filter, but does not spawn any new threads. (Note: This is just the vector cast of primalsieve::Sieve.)_
Rust
fn prime_filter_section(min_num:usize, max_num: usize) -> Vec<bool>
Similar to
fn prime_filter, but just for numbers between min and max, returned in a vector of length max-min.
Rust
fn prime_filter_section_concurrently(min_num: usize, max_num: usize, threads: usize) -> Vec<bool>
Similar to
fn prime_filter_section, but allows for a custom number of threads.
Rust
fn prime_filter_section_sequentially(min_num: usize, max_num: usize) -> Vec<bool>
Similar to
fn prime_filter_section, but does not spawn any new threads.
concurrent_prime_sieve::collectionRust
fn primes(max_num: usize) -> Vec<usize>
Generates a vector collection of primes strictly less than max_num.
The number of threads is based on the number of virtual cores detected.
Rust
fn primes_concurrently(max_num:usize, threads:usize) -> Vec<usize>
Similar to
fn primes, but allows for a custom number of threads.
Rust
fn primes_sequentially(max_num: usize) -> Vec<usize>
Similar to
fn primes, but does not spawn any new threads. (Note: This is just a vector cast of the primalsieve::SievePrimes.)_
Rust
fn primes_section(min_num: usize, max_num: usize) -> Vec<usize>
Generates a vector collection of primes between minnum and maxnum.
The number of threads is based on the number of virtual cores detected.
Rust
fn primes_section_concurrently(min_num:usize, max_num:usize, threads:usize) -> Vec<usize>
Similar to
fn primes_section, but allows for a custom number of threads.
Rust
fn primes_section_sequentially(min_num:usize, max_num:usize, threads:usize) -> Vec<usize>
Similar to
fn primes_section, but does not spawn any new threads.