Struct prime_data::PrimeData

pub struct PrimeData { /* fields omitted */ }

An abstraction over storing prime numbers

Stores whether a number is prime or not, as a bit being one or zero. Each bit corresponds to some number that is coprime with 30. This is to avoid trivial nonprimes such as even numbers, or multiples of 3 or 5. In every integer range [30k, 30(k+1)) there are 8 of those numbers. If we take them modulo 30, we’ll have a set that in this library, I call k-values.

To learn more about this struct and this library as a whole, read the guide.

Fields

• Data - The bit data of wether numbers are prime or not
• Range - What range of integers this data has about primes

They’re both private fields for the sake of abstraction. The Range can be accessed through the PrimeData::range method. The data itself, as it is merely a huge collection of bits, cannot be accessed raw. However, all of the basic information you could need to reach (such as counting the amount of prime numbers, verify if a number is prime or not, or even iterate over its prime numbers) can be done through its other methods.

Creating PrimeData

There are two basic ways of generating prime number data

1. PrimeData::generate

The simplest one. Just give that function a range and it’ll return a PrimeData instance with all primes that lie in the range you gave.

2. PrimeData::expand

If you already have some PrimeData that has all primes until some number N, and you want to gather some new PrimeData that ranges up to N², it’s more efficient to use the data you already have to “expand” into the new one you want.

In fact, the generator method is just an abstraction over the expand function. What it does is, it calls the PrimeData::new method to generate prime numbers below 30, then expands it into bigger and bigger data until it hits sqrt(N), where N is the upper bound of the data you’re trying to generate. Finally, it does one last expansin from sqrt(N) to N.

Implementations

impl PrimeData

pub fn new() -> Self

Creates a new piece of “starter data”, which are all the primes below 30

If you wish to create some starter data that gets primes below some number bigger than 30, see PrimeData::generate.

Examples

use prime_data::PrimeData;
let new = PrimeData::new();
let gen = PrimeData::generate(0..=30);
 
assert_eq!(       new.range(), gen.range());
assert_eq!(new.count_primes(), gen.count_primes());
assert_eq!(  new.is_prime(29), gen.is_prime(29));

pub fn generate(range: RangeInclusive<u64>) -> Self

Generates PrimeData with all prime numbers between the given range

Examples

use prime_data::PrimeData;
let data = PrimeData::generate(0..=100);
 
assert!( data.is_prime(2));
assert!(!data.is_prime(49));
 
assert_eq!(data.range(), (0, 100));
assert_eq!(data.count_primes(), 25);

pub fn try_iter<'a>(
    &'a self,
    range: RangeInclusive<u64>
) -> PrimeResult<PrimeIter<'a>>

Tries to create an iterator over the given range

Returns a NotEnoughData error if the given range falls out of the data (self) range.

See PrimeData::iter.

pub fn iter<'a>(&'a self, range: RangeInclusive<u64>) -> PrimeIter<'a>

Creates an iterator over the given range

Will iterate over all primes in the given range. See Self::try_iter if you wish to return an error instead of panicking.

If you wish to iterate over all primes within the given range, see PrimeData::iter_all.

Panics

Panics if the given range falls out of the data (self) range.

Examples

use prime_data::PrimeData;
let data = PrimeData::generate(0..=1000);
let mut iter = data.iter(472..=491);
 
assert_eq!(iter.next(), Some(479));
assert_eq!(iter.next(), Some(487));
assert_eq!(iter.next(), Some(491));
assert_eq!(iter.next(), None);

// fun fact: the biggest gap between to primes up to 1000 is 20,
// and it happens between 887 and 907
let mut iter = data.iter(888..=906);
 
assert_eq!(iter.next(), None);

pub fn iter_all<'a>(&'a self) -> PrimeIter<'a>

Iterates over all prime numbers in the given data.

This is useful if you wish to collect all of the data’s primes into a vector.

Warning: PrimeData are meant to be really condensed, so when you extract raw prime vectors from it, it could grow in size up to 8 times as itself. So collect this iterator carefully!

If you wish to iterate over primes within a specific range, see PrimeData::iter

Examples

use prime_data::PrimeData;
let data = PrimeData::generate(472..=491);
let mut iter = data.iter_all();
 
assert_eq!(iter.next(), Some(479));
assert_eq!(iter.next(), Some(487));
assert_eq!(iter.next(), Some(491));
assert_eq!(iter.next(), None);

pub fn try_expand(&self, range: RangeInclusive<u64>) -> PrimeResult<Self>

Tries to expand the current PrimeData into more PrimeData

The expanded data will contain all primes in range

Returns a NotEnoughData error if the given range falls out of the data (self) range.

See PrimeData::expand.

pub fn expand(&self, range: RangeInclusive<u64>) -> Self

Expands the current PrimeData into more PrimeData

The expanded data will contain all primes in the given range.

See PrimeData::try_expand if you wish to return an error instead of panicking.

Panics

Panics if the given PrimeData does not have enough data to expand into the given range.

More specifically, if you wish to expand it to some prime data with range (X..=Y), the PrimeData (self) must have a range from 7 to √Y or more.

Examples

use prime_data::PrimeData;
 
let starter_data = PrimeData::new();
let expanded_data = starter_data.expand(59..=90);
 
assert_eq!(
    expanded_data.iter_all().collect::<Vec<u64>>(),
    vec![59, 61, 67, 71, 73, 79, 83, 89]
);

pub fn range(&self) -> (u64, u64)

Destructures the PrimeData range into (start, end)

Note: The range is inclusive.

Examples

use prime_data::PrimeData;
let expansion = PrimeData::generate(173..=244);
assert_eq!(expansion.range(), (173, 244));

pub fn offset(&self) -> usize

Retrieves the PrimeData offset

PrimeData stores its raw data based on its range. The data starts at ⌊ range.start / 30 ⌋

To learn more, read the guide

Examples

use prime_data::PrimeData;
let data = PrimeData::new();
 
assert_eq!(data.expand(29..=100).offset(), 0);
assert_eq!(data.expand(30..=100).offset(), 1);
assert_eq!(data.expand(59..=100).offset(), 1);

pub fn try_is_prime(&self, x: u64) -> PrimeResult<bool>

Tries to verify if the given number is prime

Returns an OutOfBounds error if the data range does not contain x.

See PrimeData::is_prime

pub fn is_prime(&self, x: u64) -> bool

Verifies if the given number is prime

Note: If your data starts below 7, it’s heavily recommended to use the check_primes method instead. This is because this method requires the given parameter to lie within the data range. But the other only requires that the data range includes 7..=sqrt(parameter).

See PrimeData::try_is_prime if you wish to return an error instead of panicking.

Panics

Panics if it falls out of the data range

use prime_data::PrimeData;
let data = PrimeData::generate(0..=900);
 
assert!( data.is_prime(727));
assert!(!data.is_prime(781));

907 is a prime number, but it’s not in the range (0..=900).

assert!(data.is_prime(907));

pub fn try_count_primes_in_range(
    &self,
    range: RangeInclusive<u64>
) -> PrimeResult<u64>

Tries to count the amount of prime numbers in a given range

Returns a NotEnoughData error if the given range falls out of the data (self) range.

See PrimeData::count_primes_in_range.

pub fn count_primes_in_range(&self, range: RangeInclusive<u64>) -> u64

Counts the amount of prime numbers in a given range

Keep in mind that if the range start is greater than the range end, Rust interprets that as an empty range, and this function will return zero.

See PrimeData::try_count_primes_in_range if you wish to return an error instead of panicking.

Examples

use prime_data::PrimeData;
let data = PrimeData::new();
 
assert_eq!(data.count_primes_in_range(0..=30), 10);
assert_eq!(data.count_primes_in_range(2..=7),   4);
assert_eq!(data.count_primes_in_range(2..=2),   1);
assert_eq!(data.count_primes_in_range(24..=26), 0);
assert_eq!(data.count_primes_in_range(30..=0),  0);

pub fn count_primes(&self) -> u64

Counts the amount of prime numbers in the entire data

If you wish to only count primes within a specific range, see PrimeData::count_primes_in_range.

Examples

use prime_data::PrimeData;
let below_30   = PrimeData::new();
let below_100  = below_30.expand(0..=100);
let below_1000 = below_100.expand(0..=1000);
 
assert_eq!(below_30.count_primes(), 10);
assert_eq!(below_100.count_primes(), 25);
assert_eq!(below_1000.count_primes(), 168);

pub fn is_empty(&self) -> bool

Verifies if the data is empty.

Returns true if and only if the the range end is greater than the range start.

Examples

use prime_data::PrimeData;
 
assert!(!PrimeData::generate(17..=71).is_empty());
assert!(!PrimeData::generate(29..=29).is_empty());
assert!( PrimeData::generate(31..=30).is_empty());

pub fn try_nth_prime(&self, nth: u64) -> PrimeResult<u64>

Tries to find the nth prime using the given data

Returns a NotEnoughData error in two situations:

• The data starts anywhere after 7: This function requires that we count all primes up to some bound, so we need the range to start at the beginning. Anywhere <= 7 suffices.
• The data doesn’t have n primes: Naturally, if we want the 1000th prime, we can’t retrieve it if the data only has 999.

Returns an OutOfBounds error if nth is zero.

See Self::nth_prime

pub fn nth_prime(&self, nth: u64) -> u64

Retrieves the nth prime number from some data

If we call “nth prime number” as p(n), we have that p(1) = 2, because 2 is the first prime number. p(2) = 3, and so on. Therefore, the “zeroth” prime number is not defined.

See Self::try_nth_prime if you wish to return an error instead of panicking.

Panics

Panics in the following situations:

• nth is zero
• PrimeData (self) starts after 7
• PrimeData (self) ends before nth

Examples

use prime_data::PrimeData;
let data = PrimeData::generate(7..=105_000);
 
assert_eq!(data.nth_prime(1), 2);
assert_eq!(data.nth_prime(4), 7);
assert_eq!(data.nth_prime(19), 67);
assert_eq!(data.nth_prime(10001), 104743);

pub fn try_check_prime(&self, x: u64) -> PrimeResult<bool>

Tries to verify if the given number is prime

Returns a NotEnoughData error if both are true:

• The data range does not include x
• The data range does not contain the range between 7 and √x

See Self::check_prime

pub fn check_prime(&self, x: u64) -> bool

Verifies if the given number is prime

If we have information of all prime numbers between 0 and √x, we can verify if x is prime by checking if none of those primes divide x. Therefore, when calling this function, if x lies inside the data, it’s O(1), but if the data has information about all primes up to √x, it’s O(n).

See Self::try_check_prime if you wish to return an error instead of panicking.

Panics

Panics if both are true:

• The data range does not include x
• The data range does not contain the range between 7 and √x

Examples

use prime_data::PrimeData;
 
let data = PrimeData::generate(7..=35);
 
assert!( data.check_prime(7));  // O(1)
assert!(!data.check_prime(35)); // O(1)
assert!( data.check_prime(1123));  // O(n)
assert!(!data.check_prime(1225));  // O(n)

pub fn try_factorize(&self, x: u64) -> PrimeResult<Factorization>

Tries to factorize the given number into prime factors.

Returns a NotEnoughData error if the data (self) range does not contain the range 2..=sqrt(x).

See Self::factorize

pub fn factorize(&self, x: u64) -> Factorization

Factorizes the given number into prime factors.

See Self::try_factorize if you wish to return an error instead of panicking.

Panics

Panics if the data (self) range does not contain the range 2..=sqrt(x).

Examples

This function returns a Factorization struct. Read to the struct’s documentation for its methods and examples.

Trait Implementations

impl Debug for PrimeData

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.