Introduction
You bought a big box of random computer parts at a garage sale.
You’ve started putting the parts together to build custom computers.
You want to test the performance of different combinations of parts, and decide to create your own benchmarking program to see how your computers compare.
You choose the famous “Sieve of Eratosthenes” algorithm, an ancient algorithm, but one that should push your computers to the limits.
Instructions
Instructions
Your task is to create a program that implements the Sieve of Eratosthenes algorithm to find all prime numbers less than or equal to a given number.
A prime number is a number larger than 1 that is only divisible by 1 and itself.
For example, 2, 3, 5, 7, 11, and 13 are prime numbers.
By contrast, 6 is not a prime number as it not only divisible by 1 and itself, but also by 2 and 3.
To use the Sieve of Eratosthenes, first, write out all the numbers from 2 up to and including your given number.
Then, follow these steps:
- Find the next unmarked number (skipping over marked numbers).
This is a prime number.
- Mark all the multiples of that prime number as not prime.
Repeat the steps until you’ve gone through every number.
At the end, all the unmarked numbers are prime.
The Sieve of Eratosthenes marks off multiples of each prime using addition (repeatedly adding the prime) or multiplication (directly computing its multiples), rather than checking each number for divisibility.
The tests don't check that you've implemented the algorithm, only that you've come up with the correct primes.
Example
Let’s say you’re finding the primes less than or equal to 10.
-
Write out 2, 3, 4, 5, 6, 7, 8, 9, 10, leaving them all unmarked.
2 3 4 5 6 7 8 9 10
-
2 is unmarked and is therefore a prime.
Mark 4, 6, 8 and 10 as “not prime”.
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3 is unmarked and is therefore a prime.
Mark 6 and 9 as not prime (marking 6 is optional - as it’s already been marked).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4 is marked as “not prime”, so we skip over it.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5 is unmarked and is therefore a prime.
Mark 10 as not prime (optional - as it’s already been marked).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6 is marked as “not prime”, so we skip over it.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7 is unmarked and is therefore a prime.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8 is marked as “not prime”, so we skip over it.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9 is marked as “not prime”, so we skip over it.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10 is marked as “not prime”, so we stop as there are no more numbers to check.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
You’ve examined all the numbers and found that 2, 3, 5, and 7 are still unmarked, meaning they’re the primes less than or equal to 10.
Dig Deeper
ranges and filter_map
Ranges and filter-map()
pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
let mut numbers: Vec<_> = (0..=upper_bound).map(Option::from).collect();
let upper_bound = upper_bound as usize;
(2..numbers.len())
.filter_map(|i| {
let prime = numbers[i].take()? as usize;
(prime * prime..=upper_bound)
.step_by(prime)
.for_each(|j| numbers[j] = None);
Some(prime as u64)
})
.collect()
}
This approach starts by defining a Vec of Some values from 0 through the upper bound.
To minimize type conversions, the upper bound is redefined as a usize.
A Range is defined that goes from 2 through the length of the Vec.
Each number from the range is passed to the filter_map().
The closure (also known as a lambda) in the body of the filter_map() uses the take() method, combined with the
unwrap operator (?), to get the element value in the Vec at the index of the number passed in from the range.
If the element value is None, then no further processing happens in the lambda for that iteration.
If the element value is Some number, then an inner range is defined, starting from the element value times itself and going through the upper bound.
The step_by() method is used to traverse the range in steps the size of the element value.
Each number from the inner range is passed to the for_each() method.
The lambda inside the for_each sets None as the value for the element in the Vec at the index of the value passed in.
After the inner range is done, the filter_map() lambda returns the element value rewrapped in a Some as type u64.
After the outer range is done, all of the Some values are collected from the Vec and returned.
Type inference is used to return the values as a type Vec<u64>.
for in ranges with filter
for in ranges with filter()
pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
let mut work: Vec<u64> = (0..=upper_bound).collect();
work[1] = 0;
let stop = (upper_bound as f64).sqrt() as usize + 1usize;
let upper_bound = upper_bound as usize;
for i in 2..stop {
if (work[i]) != 0 {
for idx in (i * i..=upper_bound).step_by(i) {
work[idx] = 0;
}
}
}
work.iter().filter(|num| *num != &0u64).copied().collect()
}
This approach starts by defining a Vec of values from 0 through the upper bound.
Since numbers below 2 are not valid primes, the element at index 1 is set to 0.
Since squares of numbers are processed, the sqrt() method is used to determine when iterating the Vec indexes will stop.
To minimize type conversions, the upper bound is redefined as a usize.
A for in range is defined from 2 up to but not including the stop value.
Each number in the range is used inside the loop as an index to test if the element value in the Vec at that index is not 0.
If the element value is not 0, then an inner for in range is defined, starting with the number times itself and going through the upper bound.
The step_by() method is used to traverse the range in steps the size of the outer range number.
Each number from the inner range is used as an index to set the element value at that index in the Vec to 0.
When the outer range is done, the Vec is passed through the iter() method to the filter() method.
The closure (also known as a lambda) in the body of the filter() tests that the element is not 0.
It dereferences the number to convert it from a “reference to a reference” to a “reference”, and it references the 0 literal
u64 value to enable comparison between references.
The surviving values are chained to the copied() method, which changes the iterator of references to an iterator of the copied values.
The copied values ae chained to the collect() method, which uses type inference to return the Vec<u64>.
Source: Exercism rust/sieve