Struct primesieve::Sieve
[−]
[src]
pub struct Sieve { /* fields omitted */ }A structure which sieves for primes up to a given limit and stores the results for later iteration and querying.
Methods
impl Sieve[src]
fn is_prime(&self, n: u64) -> Result<bool, ()>
Returns whether or not n is a prime number, or Err(()) if n is larger than the square
of the largest prime held in the sieve.
Uses a simple lookup if n is not greater than the largest number known about by the
sieve, and uses trial division otherwise.
Examples
let sieve = primesieve::Sieve::to_limit(100); assert_eq!(sieve.is_prime(0), Ok(false)); assert_eq!(sieve.is_prime(1), Ok(false)); assert_eq!(sieve.is_prime(2), Ok(true)); assert_eq!(sieve.is_prime(3), Ok(true)); assert_eq!(sieve.is_prime(4), Ok(false)); assert_eq!(sieve.is_prime(5), Ok(true)); assert_eq!(sieve.is_prime(491), Ok(true)); assert_eq!(sieve.is_prime(493), Ok(false)); assert_eq!(sieve.is_prime(495), Ok(false)); assert_eq!(sieve.is_prime(497), Ok(false)); assert_eq!(sieve.is_prime(499), Ok(true)); assert_eq!(sieve.is_prime(1000001), Err(()));
fn factorise(&self, n: u64) -> Result<Vec<(u64, u64)>, (u64, Vec<(u64, u64)>)>
Factorises n into (prime, exponent) pairs.
Returns Err(remainder, partial factorisation) if n cannot be fully factorised without
sieving for more primes.
If x is the largest number known about by the sieve, then any integer having at most one
prime factor larger than x can be factorised. In particular, any number not greater than
x^2 can be factorised.
Examples
let sieve = primesieve::Sieve::to_limit(100); assert_eq!(sieve.factorise(2), Ok(vec![(2, 1)])); assert_eq!(sieve.factorise(4), Ok(vec![(2, 2)])); assert_eq!(sieve.factorise(1 << 63), Ok(vec![(2, 63)])); assert_eq!(sieve.factorise(2 * 3), Ok(vec![(2, 1), (3, 1)])); assert_eq!(sieve.factorise(89 * 97), Ok(vec![(89, 1), (97, 1)])); assert_eq!(sieve.factorise(8 * 9 * 5), Ok(vec![(2, 3), (3, 2), (5, 1)])); assert_eq!(sieve.factorise(2 * 3 * 5 * 991), Ok(vec![(2, 1), (3, 1), (5, 1), (991, 1)])); assert_eq!(sieve.factorise(2 * 3 * 5 * 991 * 991), Err((991 * 991, vec![(2, 1), (3, 1), (5, 1)])));
fn euler_phi(&self, n: u64) -> Result<u64, ()>
Calculates the value of Euler's totient function ϕ at n.
Uses the formula based on the factorisation of n, that is ϕ(n) is equal to n times
the product of 1 - 1/p, where p ranges over the distinct prime factors of n.
Returns Err(()) if n cannot be factorised without first sieving for more primes.
Examples
let sieve = primesieve::Sieve::to_limit(100); assert_eq!(sieve.euler_phi(2), Ok(1)); assert_eq!(sieve.euler_phi(4), Ok(2)); assert_eq!(sieve.euler_phi(1 << 63), Ok(1 << 62)); assert_eq!(sieve.euler_phi(2 * 3), Ok(2)); assert_eq!(sieve.euler_phi(89 * 97), Ok(88 * 96)); assert_eq!(sieve.euler_phi(8 * 9 * 5), Ok(4 * 6 * 4)); assert_eq!(sieve.euler_phi(2 * 3 * 5 * 991), Ok(2 * 4 * 990)); assert_eq!(sieve.euler_phi(2 * 3 * 5 * 991 * 991), Err(()));
fn number_of_divisors(&self, n: u64) -> Result<u64, ()>
Calculates the number of divisors of n.
Returns Err(()) is n cannot be fully factorised without first sieving for more primes.
This uses the well-known formula, that if n is given in factorised form as a product
p_i ^ a_i, then the number of divisors of n is given by:
(a_1 + 1)(a_2 + 1) ... (a_k + 1)
Examples
let sieve = primesieve::Sieve::to_limit(100); assert_eq!(sieve.number_of_divisors(2), Ok(2)); assert_eq!(sieve.number_of_divisors(4), Ok(3)); assert_eq!(sieve.number_of_divisors(1 << 63), Ok(64)); assert_eq!(sieve.number_of_divisors(2 * 3), Ok(2 * 2)); assert_eq!(sieve.number_of_divisors(89 * 97), Ok(2 * 2)); assert_eq!(sieve.number_of_divisors(8 * 9 * 5), Ok(4 * 3 * 2)); assert_eq!(sieve.number_of_divisors(2 * 3 * 5 * 991), Ok(2 * 2 * 2 * 2)); assert_eq!(sieve.number_of_divisors(2 * 3 * 5 * 991 * 991), Err(()));
impl Sieve[src]
fn to_limit(limit: u64) -> Sieve
Create a new Sieve which knows about the primes up to the given limit.
fn to_n_primes(n: usize) -> Sieve
Create a new Sieve which knows about at least the first n primes.
fn limit(&self) -> u64
Returns the highest number that this Sieve knows about. Note that this may be slightly
larger than the limit the sieve was created with.
Examples
let sieve = primesieve::Sieve::to_limit(1000); assert!(sieve.limit() >= 1000);
fn num_primes(&self) -> usize
Returns the number of primes that this Sieve knows about. Note that this may be slightly
higher than the number of primes the sieve was created with.
Examples
let sieve = primesieve::Sieve::to_n_primes(1000); assert!(sieve.num_primes() >= 1000);
fn nth_prime(&self, n: usize) -> Option<u64>
Returns the nth prime number, indexed from 0, or None if fewer than n prime numbers
are held in the sieve.
Examples
let sieve = primesieve::Sieve::to_n_primes(100); assert_eq!(sieve.nth_prime(0), Some(2)); assert_eq!(sieve.nth_prime(1), Some(3)); assert_eq!(sieve.nth_prime(2), Some(5)); assert_eq!(sieve.nth_prime(3), Some(7)); assert_eq!(sieve.nth_prime(4), Some(11)); assert_eq!(sieve.nth_prime(97), Some(521)); assert_eq!(sieve.nth_prime(98), Some(523)); assert_eq!(sieve.nth_prime(99), Some(541)); assert_eq!(sieve.nth_prime(1000), None);
impl<'a> Sieve[src]
fn iter(&'a self) -> SieveIterator<'a>
Return an iterator over the primes in this Sieve.
Examples
let sieve = primesieve::Sieve::to_limit(100); assert_eq!(sieve.iter().take_while(|&x| x < 100).collect::<Vec<u64>>(), vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]);