Some pretty naive Erastothenes' Sieve implementations in Rust

multiple-sieves.rs

use bitvec::prelude::*;

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}

pub fn sieve_ints(len: usize) {
    let mut count: usize = 0;
    const MAX: usize = 8192;
    let mut flags: [usize; MAX + 1] = [0; MAX+1];
    for _ in 0..len {
        count = 0;
        for i in 2..MAX {
            flags[i] = 1;
        }
        for num in 2..MAX {
            if flags[num] == 1 {
                // for k in ((i+i)..MAX).step_by(i) {
                //     flags[k] = 0;
                // }
                'mul: for factor in num .. {
                    let product = num * factor;
                    if product >= MAX {
                        break 'mul;
                    }
                    flags[product] = 0;
                }  
                count += 1;
            }
        }
    }
    println!("Count: {}", count);
}

pub fn sieve_bools(len: usize) {
    let mut count: usize = 0;
    const MAX: usize = 8192;
    let mut flags: [bool; MAX + 1] = [false; MAX+1];
    for _ in 0..len {
        count = 0;
        for i in 2..MAX {
            flags[i] = true;
        }
        for num in 2..MAX {
            if flags[num] {
                // for k in ((i+i)..MAX).step_by(i) {
                //     flags[k] = false;
                // }
                'mul: for factor in num .. {
                    let product = num * factor;
                    if product >= MAX {
                        break 'mul;
                    }
                    flags[product] = false;
                }  
                count += 1;
            }
        }
    }
    println!("Count: {}", count);
}

pub fn sieve_bits(len: usize) {
    let mut count: usize = 0;
    const MAX: usize = 8192;
    // let mut flags: [bool; MAX + 1] = [false; MAX+1];
    let mut flags = BitVec::<LocalBits, u8>::repeat(true, MAX);
                                                     // ^ usize -> u8 == 10s -> 8.2s
    
    // let flagslice = flags.as_mut_bitslice();
    // let mut flags: BitArray<Msb0, u8> = BitArray::<Msb0, u8>::zeroed();
    for _ in 0..len {
        count = 0;
        flags.set_all(true);
        // ^ 15 sec -> 13 sec
        // for i in 2..MAX {
        //     flagslice.set(i, true);
        // }
        for num in 2..MAX {
            if flags[num] {
                'mul: for factor in num .. {
                    let product = num * factor;
                    if product >= MAX {
                        break 'mul;
                    }
                    flags.set(product, false);
                }                
                // ^ 15 -> 10 sec
                // for k in ((i+i)..MAX).step_by(i) {
                //     flagslice.set(k, false);
                // }
                // 
                count += 1;
            }
        }
    }
    println!("Count: {}", count);
}

performance.txt

old revision:
sieve usize             time:   [6.7478 s 6.8638 s 6.9397 s]
sieve bool              time:   [5.1882 s 5.1956 s 5.2043 s]
sieve bits              time:   [8.6145 s 8.8901 s 9.1595 s]

switching from a stepping flag-setter to a simple multiplier with bounds check:

sieve usize             time:   [4.7122 s 4.8028 s 4.8955 s]
sieve bool              time:   [3.3338 s 3.4177 s 3.4761 s]

that's a -30% diff
// sieve bits was already using this