Struct primal::Sieve
[−]
[src]
pub struct Sieve {
// some fields omitted
}A heavily optimised prime sieve.
This stores information about primes up to some specified limit,
allowing efficient queries of information about them. This caches
the successive outputs of StreamingSieve and has very similar
performance, modulo the differences in memory use: to cache the
information Sieve uses approximately limit / 30 + O(sqrt(limit)) bytes of memory. Consider directly using
StreamingSieve if repeated queries are unnecessary, since that
uses only O(sqrt(limit)) bytes.
Examples
let sieve = primal::Sieve::new(10_000_000); assert_eq!(sieve.prime_pi(123456), 11601); assert!(sieve.is_prime(6395047)); assert!(!sieve.is_prime(6395048));
Methods
impl Sieve
fn new(limit: usize) -> Sieve
Create a new instance, sieving out all the primes up to
limit.
fn upper_bound(&self) -> usize
Return the largest number that this sieve knows about.
It will be at least as large as the number passed to new,
but may be slightly larger.
Examples
let sieve = primal::Sieve::new(1000); assert!(sieve.upper_bound() >= 1000);
fn is_prime(&self, n: usize) -> bool
Determine if n is a prime number.
Panics
If n is out of range (greater than self.upper_bound()),
is_prime will panic.
Examples
let sieve = primal::Sieve::new(1000); assert_eq!(sieve.is_prime(0), false); assert_eq!(sieve.is_prime(1), false); assert_eq!(sieve.is_prime(2), true); assert_eq!(sieve.is_prime(3), true); assert_eq!(sieve.is_prime(4), false); assert_eq!(sieve.is_prime(5), true); assert_eq!(sieve.is_prime(991), true); assert_eq!(sieve.is_prime(993), false); assert_eq!(sieve.is_prime(995), false); assert_eq!(sieve.is_prime(997), true); assert_eq!(sieve.is_prime(999), false);
fn prime_pi(&self, n: usize) -> usize
Count the number of primes upto and including n.
Panics
If n is out of range (greater than self.upper_bound()),
prime_pi will panic.
Examples
let sieve = primal::Sieve::new(1000); assert_eq!(sieve.prime_pi(10), 4); // the endpoint is included assert_eq!(sieve.prime_pi(11), 5); assert_eq!(sieve.prime_pi(100), 25); assert_eq!(sieve.prime_pi(1000), 168);
fn factor(&self, n: usize) -> Result<Vec<(usize, usize)>, (usize, Vec<(usize, usize)>)>
Factorise n into (prime, exponent) pairs.
Returns Err((leftover, partial factorisation)) if n cannot
be fully factored, or if n is zero (leftover == 0). A
number can not be completely factored if and only if the prime
factors of n are too large for this sieve, that is, if there
is
- a prime factor larger than
U^2, or - more than one prime factor between
UandU^2
where U is the upper bound of the primes stored in this
sieve.
Notably, any number between U and U^2 can always be fully
factored, since these numbers are guaranteed to only have zero
or one prime factors larger than U.
Examples
let sieve = primal::Sieve::new(100); assert_eq!(sieve.factor(2), Ok(vec![(2, 1)])); assert_eq!(sieve.factor(4), Ok(vec![(2, 2)])); assert_eq!(sieve.factor(1 << 31), Ok(vec![(2, 31)])); assert_eq!(sieve.factor(18), Ok(vec![(2, 1), (3, 2)])); assert_eq!(sieve.factor(25 * 81), Ok(vec![(3, 4), (5, 2)])); // "large" prime factors are OK, as long as there's only one assert_eq!(sieve.factor(2 * 3 * 97 * 97 * 991), Ok(vec![(2, 1), (3, 1), (97, 2), (991, 1)])); // too many large factors is problematic assert_eq!(sieve.factor(991 * 991), Err((991 * 991, vec![]))); assert_eq!(sieve.factor(2 * 3 * 97 * 97 * 991 * 991), Err((991 * 991, vec![(2, 1), (3, 1), (97, 2)])));
fn nth_prime(&self, n: usize) -> usize
Compute pn, the n prime number, 1-indexed
(i.e. p1 = 2, p2 = 3).
Panics
n must be larger than 0 and less than the total number of
primes in this sieve (that is,
self.prime_pi(self.upper_bound())).
Example
let (_, hi) = primal::estimate_nth_prime(1_000); let sieve = primal::Sieve::new(hi as usize); assert_eq!(sieve.nth_prime(10), 29); assert_eq!(sieve.nth_prime(100), 541); assert_eq!(sieve.nth_prime(1_000), 7919);
fn primes_from(&'a self, n: usize) -> SievePrimes<'a>
Return an iterator over the primes from n (inclusive) to the
end of this sieve.
NB. it is not guaranteed that the end is the same as the limit
passed to new: it may be larger. Consider using take_while
if the limit must be exact.
Panics
If n is out of range (greater than self.upper_bound()),
prime_pi will panic.
Examples
let sieve = primal::Sieve::new(1_000); // print the three digit primes for p in sieve.primes_from(100).take_while(|x| *x < 1000) { println!("{}", p); }