use std::time::Duration;
use std::time::Instant;
use thousands::Separable;

// this project available at: https://arachnoid.com/files/python01/

// See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

fn my_prime_sieve(top: usize) -> Vec<usize> {
    // create sieve array, initial values all true
    let mut sieve: Vec<bool> = vec![true; top];
    // create list of primes for caller
    let mut primes: Vec<usize> = vec![];
    // add 2 to initial list
    primes.push(2);
    // start at 3, step by 2, meaning odd numbers only
    for i in (3..top).step_by(2) {
        // if i is prime
        if sieve[i] {
            // add i to prime list
            primes.push(i);
            // mark all multiples of i as composite
            // because each has i as a factor
            for j in ((i * i)..top).step_by(i) {
                sieve[j] = false;
            }
        }
    }
    return primes;
}

fn main() {
    let top: usize = 1_000_000;
    let  now: Instant = Instant::now();
    let  primes: Vec<usize> = my_prime_sieve(top);
    let  elapsed: Duration = now.elapsed();
    println!("Elapsed time in my_prime_sieve(): {elapsed:.2?}");
    let pl: usize = primes.len();
    let pl_str: String = pl.separate_with_commas();
    let top_str: String = top.separate_with_commas();
    println!("Primes in range <= p < {top_str}: {pl_str}");
    if top <= 200 {
        println!("List of primes in range <= p < {top_str}: {primes:?}");
    }
}