Function prime_suspects::segmented_sieve

pub fn segmented_sieve(max_val: usize, segment_size: usize) -> Vec<usize>

A segmented approach to sieveing, keeping memory use to O(√n). As Sorensen states, this is the most practical optimization to the sieve of Eratosthenes.

Examples

Compute the last three primes up to 2⁶⁴ + 1. (The segmented sieve functions call eratosthenes_sieve for lower values for reasons of efficiency.)

assert_eq!(vec![65521, 65519, 65497],
           prime_suspects::segmented_sieve(65537, 256)
             .into_iter().rev().take(3)
             .collect::<Vec<usize>>());