Rayon isn't any faster than loop despite 16x more CPU usage

I have made a prime number calculator and I don't get the speed increase from rayon I'd expect. Here is the simple code behind it:

let max = args()
    .nth(1)
    .ok_or(eyre!("No argument provided"))?
    .parse::<usize>()?;
let mut primes: Vec<bool> = vec![true; max + 1];
primes[0] = false;
primes[1] = false;
let max_check = (max as f32).sqrt().ceil() as usize;

eprintln!("Finding primes up to {}...", max);
for i in 2..=max_check {
    if primes[i] {
        // Single-threaded
        let mut j = 2;
        while i * j <= max {
            primes[i * j] = false;
            j += 1;
        }
        // Multithreaded using rayon
        primes
            .par_iter_mut()
            .skip(i * 2)
            .step_by(i)
            .for_each(|is_prime| *is_prime = false)
    }
}

It is a basic Sieve of Eratosthenes.

In the multithreaded version the work of turning multiples of i into non-primes is spread across all 16 threads of my computer, however the execution time of both methods are essentially the same, even though every core is maxed out in the multithreaded version.

Any idea why I don't get a 16x speed increase? Does it have to do with rayon or is my code just bad?

I have about 1 billion booleans in my array, so rayon seems like a good idea