Primes
primes is a command-line interface for finding prime numbers, using the ancient and elegant Sieve of Eratosthenes. It’s a simple example of a Rust program and how darned fast Rust can be. I use it often in various config files and cronjobs, in order to mitigate the Thundering Herd problem.
When I come across values like 1009 or 3593 in config files, it serves as a quick clue that I’ve been there, surveyed the land, and made my mark. As the building blocks of all the integers, primes are holy. Working with them is a joy. It’s a communion with eternal mysteries. This is my journey in creating primes.
Planning & Analysis
What are my goals? They are this:
- I want to have fun learning Rust, specifically Edition 2024
- I want to see how performant my solution is (ie: include benchmarks)
- I want to implement the algorithm myself
- A CLI that finds prime numbers, aside from being fun to build, could be useful
Requirements
The basic API will look like this:
Primes Near
primes near takes one number as input and returns the nearest prime lower than that number, and the nearest prime higher. If the number you give it is itself prime, it returns 3 numbers.
primes near 25 # returns 23,27primes near 13 # returns 11,13,17primes near banana # panics, because banana is not a number
Primes Between
Takes two numbers (unsigned integers) and returns all the primes in that range, inclusive.
primes between 17 29 # returns 17,23,29primes between 65000 65100 # returns 65003,65011...65089,65099
Primes Beneath
Return all primes below a certain number.
primes beneath 17 # returns 2,3,5,7,11,13,17
Primes Is
Your basic primality test.
primes is 17 # returns yes
Design
A simple crate which can be easily installed using cargo, producing either a binary executable or Rust library, depending on what you want.
├── benches
│ └── example.rs <-- benchmarks
├── Cargo.toml
├── README.md
├── src
│ ├── lib.rs <-- core logic
│ ├── main.rs <-- CLI
│ └── test.rs <-- unit tests
└── target
├── criterion <-- benchmark data
├── debug
└── release <-- binaries
Development
Let’s set up our IDE and get the nightly version of rust:
rustup toolchain install nightlyrustup default nightly
All the interesting logic is in ./src/lib.rs. Let’s start with beneath() which finds all prime numbers beneath a certain number. This will be the workhorse that powers all other functionality and where all our optimisations hinge.
// ./src/lib.rs
// return all primes beneath (and maybe including) the value provided
pub fn beneath(upper: usize) -> Vec<usize> {
let mut primes: Vec<usize> = Vec::with_capacity(n_primes_beneath(upper));
for i in 2..=upper {
if !is_multiple_of(i, &primes) {
primes.push(i);
}
}
return primes;
}
There is some insight to grok here. First off, our sieve is an iterative algorithm. You find primes by process of elimination, which in the most naive sense means going through all the numbers from 0 to n and checking if they are prime. This implies a linear time operation, but another feature of factorization is commutativity, which allows us to stop iterating at the square root of a number. That implies logarithmic time. Thirdly, our final value (a list of primes), as we build it, is useful as an intermediary data structure precisely because a prime number can be defined as a number that is not divisible by a smaller prime number. How do you know every even number must be eliminated? Because 2 is a prime, so any multiple of 2 is not a prime. Extrapolating this further, we say that any number that is a multiple of a prime is not a prime. This is the core insight of the Sieve of Eratosthenes.
The helper function n_primes_beneath() allows us to pre-allocate our vector capactity efficiently, giving us good space complexity. It’s possible to estimate the number of primes beneath a certain value using this consequence of prime number theorem:
$$\pi(n) \sim \frac{n}{\log n} \ \text{as} \ n \to +\infty$$
// ./src/lib.rs
// find upper limit of number of primes beneath n
fn n_primes_beneath(n: usize) -> usize {
if n < 2 {
return 0;
}
if n == 3 {
return 1;
}
if n == 4 {
return 2;
}
let n_float = n as f64;
let approx_primes: f64 = n_float / n_float.ln() + 1 as f64;
approx_primes.ceil() as usize
}
Those are the basic primitives all other functions build on. For example between() just calls beneath() and lobs off the first bit:
// ./src/lib.rs
// call beneath() and then slice off the early bits
pub fn between(a: usize, b: usize) -> Vec<usize> {
let all_primes = beneath(b);
let mut i = 0;
for p in &all_primes {
if p < &a {
i += 1;
}
}
let slice = &all_primes[i..];
return slice.to_vec();
}
So how does primes perform? In terms of time complexity, it appears to have slightly worse than linear growth characteristics. This makes it infeasable (or at least less fun) on operations involving integers in the 1,000,000 to ∞ range.
Obviously at this stage, it’s still just a toy. It should not be used for finding really big prime numbers, as there are much more advanced algorithms and bigger computers for that, but I am dedicated to only implementing algorithms I can understand, and improving this project in ways that make sense. In the future I will look into more suitable data structures, such as BTreeSet, and run benchmarks to determine how it affects performance. My goal is to get under linear growth.
Getting started
To install, you must first have cargo. Then do:
cargo install codemonk-primes-cli
Now you have a binary called primes. You can do all the shiz.
primes near 25 # returns 23,27primes near banana # panics, because banana is not a numberprimes between 17 29 # returns 17,23,29primes beneath 17 # returns 2,3,5,7,11,13,17primes is 17 # returns yes
Including unit tests and benchmarks.
cargo test # runs all testscargo bench # runs all benchmarks
Contributions welcome 😎