Find all primes between 0 and 2^32

primes.rs

use std::time::Instant;

fn number_to_index_mask(num: u32) -> (usize, u64) {
    let num = (num - 1) / 2;
    let index = (num / 64) as usize;
    let bits = num % 64;
    (index, 1 << bits)
}

fn unmark(mask: &mut [u64], num: u32) {
    let (index, bits) = number_to_index_mask(num);
    mask[index] &= !bits;
}

fn is_prime(mask: &[u64], num: u32) -> bool {
    let (index, bits) = number_to_index_mask(num);
    mask[index] & bits == bits
}

fn unmark_multiples_of(mask: &mut [u64], num: u32) {
    // we don't need to unmark num, as it should be prime, anyway
    // num * 2 is even so it's not in our bitmask table
    // hence, we start at num * 3
    let mut current = num * 3;
    loop {
        unmark(mask, current);
        // this is just to check for overflows
        // !(num * 2) + 1 == 2^32 - 2 * num
        // if we are above it, next iteration would overflow
        if current >= !(2 * num) + 1 {
            break;
        }
        current += 2 * num;
    }
}

fn main() {
    let start = Instant::now();
    // bit mask representing all odd numbers between 0 and 2^32 - 1
    let mut prime_mask = vec![::std::u64::MAX; 33554432];
    // the bitmask contains 1 which is not prime - unmark it
    unmark(&mut prime_mask, 1);
    // every non-prime n must be divisible by a number less than sqrt(n)
    // sqrt(2^32) = 2^16 = 65536
    // we only check odd divisors, so we iterate through 32768 possibilities
    for num in 1..32768 {
        // no need to consider even divisors
        let divisor = 2 * num + 1;
        // if divisor is not prime, we already marked its multiples as non-prime
        if !is_prime(&prime_mask, divisor) {
            continue;
        }
        unmark_multiples_of(&mut prime_mask, divisor);
    }
    let end = Instant::now();
    eprintln!("Calculation time: {:?}", end - start);
    // sanity check - print the first 64bit mask as binary
    eprintln!("{:b}", prime_mask[0]);
    eprintln!("Starting output...");
    // 2 is even, hence not in the mask - print it separately
    println!("2");
    // print all the odd primes found
    for (i, mut mask) in prime_mask.into_iter().enumerate() {
        let mut number = i * 128 + 1;
        while mask != 0 {
            if mask % 2 == 1 {
                println!("{}", number);
            }
            mask >>= 1;
            number += 2;
        }
    }
}

#[test]
fn test_indexing() {
    let (index, bits) = number_to_index_mask(1);
    assert_eq!(index, 0);
    assert_eq!(bits, 1);

    let (index, bits) = number_to_index_mask(3);
    assert_eq!(index, 0);
    assert_eq!(bits, 2);

    let (index, bits) = number_to_index_mask(5);
    assert_eq!(index, 0);
    assert_eq!(bits, 4);

    let (index, bits) = number_to_index_mask(11);
    assert_eq!(index, 0);
    assert_eq!(bits, 32);

    let (index, bits) = number_to_index_mask(127);
    assert_eq!(index, 0);
    assert_eq!(bits, 1 << 63);

    let (index, bits) = number_to_index_mask(129);
    assert_eq!(index, 1);
    assert_eq!(bits, 1);
}