The iterator code came from an answer to this SO question.

I struggled with this one the most. I wanted a .each_slice() method very badly, since that was the quickest route to the same algorithm in Ruby, and asked for it on SO.

/// A [segmented
/// approach](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve)
/// to sieveing, keeping memory use to O(√n). As Sorensen states, this is the
/// most practical optimization to the sieve of Eratosthenes.
///
/// # Examples
///
/// ```
/// assert_eq!(vec![65521, 65519, 65497],
/// prime_suspects::segmented_sieve(65537, 256)
/// .iter().rev().take(3).map(|&num| num)
/// .collect::<Vec<usize>>());
/// ```
///
// ```
// assert_eq!(&999983,
// prime_suspects::segmented_sieve(1000000, 350).last().unwrap());
// ```
pub fn segmented_sieve(max_val: usize, mut segment_size: usize) -> Vec<usize> {
 if max_val <= ((2 as i64).pow(16) as usize) {
 // early return if the highest value is small enough (empirical)
 return eratosthenes_sieve(max_val);
 }
 if segment_size > ((max_val as f64).sqrt() as usize) {
 segment_size = (max_val as f64).sqrt() as usize;
 println!("Segment size is larger than √{}. Reducing to {} to keep resource use down.",
 max_val, segment_size);
 }
 // get the primes up to the first segment
 let small_primes = eratosthenes_sieve((max_val as f64).sqrt() as usize);
 let mut big_primes = small_primes.clone();
 // As Sorensen says, we need to construct a sequence over each segment, in
 // the interval [start + 1, start + segment_size] that begins with
 // (start + this_prime - ( start mod p)), and increases by p up to
 // (start + segment_size).
 // That sequence will be the values to sieve out of this_segment.
 // clunky way of doing each_slice, from
 // http://stackoverflow.com/a/37033906/2023432
 let mut segment_range = (segment_size..max_val).peekable();
 while segment_range.peek().is_some() {
 let this_segment: Vec<_> = segment_range.by_ref().take(segment_size).collect();
 let mut sieved_segment: Vec<_> = this_segment.clone();
 for &this_prime in &small_primes {
 if !this_segment.is_empty() {
 let mut starting_offset = this_segment[0] % this_prime;
 starting_offset = if starting_offset == 0 { this_prime } else { starting_offset };
 let first_val = this_segment[0] + this_prime - starting_offset;
 let last_val: &usize = this_segment.last().unwrap();
 // hack for inclusive range while RFC is figured out. see
 // https://www.reddit.com/r/rust/comments/3xkfro/what_happened_to_inclusive_ranges/
 let sieve_vec = (first_val..(*last_val + 1))
 .step(this_prime)
 .collect::<Vec<_>>();
 
 sieved_segment = sieved_segment
 .iter()
 .filter(|&check_num| !sieve_vec.contains(&check_num))
 .map(|&val| val)
 .collect::<Vec<_>>();
 
 }
 }
 for sieved_prime in sieved_segment {
 big_primes.push(sieved_prime);
 }
 }
 
 return big_primes;
}
#[test]
fn no_end_segment_sieve_misses() {
 let test_100k_primes = segmented_sieve(100000, 300);
 assert!(!test_100k_primes.contains(&99999));
 let test_100m_primes = segmented_sieve(1000000, 350);
 assert!(test_100m_primes.contains(&999983));
 assert!(!test_100m_primes.contains(&999997));
}

The iterator code came from an answer to this SO question.

I struggled with this one the most. I wanted a .each_slice() method very badly, since that was the quickest route to the same algorithm in Ruby, and asked for it on SO.

/// A [segmented
/// approach](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve)
/// to sieveing, keeping memory use to O(√n). As Sorensen states, this is the
/// most practical optimization to the sieve of Eratosthenes.
///
/// # Examples
///
/// ```
/// assert_eq!(vec![65521, 65519, 65497],
/// prime_suspects::segmented_sieve(65537, 256)
/// .iter().rev().take(3).map(|&num| num)
/// .collect::<Vec<usize>>());
/// ```
///
// ```
// assert_eq!(&999983,
// prime_suspects::segmented_sieve(1000000, 350).last().unwrap());
// ```
pub fn segmented_sieve(max_val: usize, mut segment_size: usize) -> Vec<usize> {
 if max_val <= ((2 as i64).pow(16) as usize) {
 // early return if the highest value is small enough (empirical)
 return eratosthenes_sieve(max_val);
 }
 if segment_size > ((max_val as f64).sqrt() as usize) {
 segment_size = (max_val as f64).sqrt() as usize;
 println!("Segment size is larger than √{}. Reducing to {} to keep resource use down.",
 max_val, segment_size);
 }
 // get the primes up to the first segment
 let small_primes = eratosthenes_sieve((max_val as f64).sqrt() as usize);
 let mut big_primes = small_primes.clone();
 // As Sorensen says, we need to construct a sequence over each segment, in
 // the interval [start + 1, start + segment_size] that begins with
 // (start + this_prime - ( start mod p)), and increases by p up to
 // (start + segment_size).
 // That sequence will be the values to sieve out of this_segment.
 // clunky way of doing each_slice, from
 // https://stackoverflow.com/a/37033906/2023432
 let mut segment_range = (segment_size..max_val).peekable();
 while segment_range.peek().is_some() {
 let this_segment: Vec<_> = segment_range.by_ref().take(segment_size).collect();
 let mut sieved_segment: Vec<_> = this_segment.clone();
 for &this_prime in &small_primes {
 if !this_segment.is_empty() {
 let mut starting_offset = this_segment[0] % this_prime;
 starting_offset = if starting_offset == 0 { this_prime } else { starting_offset };
 let first_val = this_segment[0] + this_prime - starting_offset;
 let last_val: &usize = this_segment.last().unwrap();
 // hack for inclusive range while RFC is figured out. see
 // https://www.reddit.com/r/rust/comments/3xkfro/what_happened_to_inclusive_ranges/
 let sieve_vec = (first_val..(*last_val + 1))
 .step(this_prime)
 .collect::<Vec<_>>();
 
 sieved_segment = sieved_segment
 .iter()
 .filter(|&check_num| !sieve_vec.contains(&check_num))
 .map(|&val| val)
 .collect::<Vec<_>>();
 
 }
 }
 for sieved_prime in sieved_segment {
 big_primes.push(sieved_prime);
 }
 }
 
 return big_primes;
}
#[test]
fn no_end_segment_sieve_misses() {
 let test_100k_primes = segmented_sieve(100000, 300);
 assert!(!test_100k_primes.contains(&99999));
 let test_100m_primes = segmented_sieve(1000000, 350);
 assert!(test_100m_primes.contains(&999983));
 assert!(!test_100m_primes.contains(&999997));
}

Code

It consists of three parts: a "SquareMultiple" iterator that computes the sequence "i^2, i^2+i, i^2 + 2i...", a sieve of Eratosthenes, and then a segmented sieve that uses multiples from the Eratosthenes sieve to sieve the rest of the numbers up to the first function argument.

SquareMultiple

Code

It consists of three parts: a SquareMultiple iterator that computes the sequence \$i^2, i^2+i, i^2 + 2i...\$, a sieve of Eratosthenes, and then a segmented sieve that uses multiples from the Eratosthenes sieve to sieve the rest of the numbers up to the first function argument.

SquareMultiple