use bit_vec::BitVec;
use std::time::Instant; // 0.5.1

fn main() {
    const MAXNUM: usize = 2_000_000;

    let now = Instant::now();
    let mut candidates = BitVec::from_elem(MAXNUM / 2, true);
    let mut curr_prime: usize = 3;
    let mut sum_primes: usize = 2;

    candidates.set(0, false);

    while (curr_prime as f64) < (MAXNUM as f64).sqrt() {
        sum_primes += curr_prime;
        ((curr_prime * curr_prime - 1) / 2..candidates.len())
            .step_by(curr_prime)
            .for_each(|x| candidates.set(x, false));

        curr_prime += candidates
            .iter()
            .skip((curr_prime + 1) / 2)
            .position(|x| x)
            .unwrap()
            * 2
            + 2;
        //print!{"{} ", curr_prime};
    }

    sum_primes += (curr_prime..)
        .step_by(2)
        .zip(candidates.iter().skip((curr_prime + 1) / 2 - 1))
        .filter_map(|(i, b)| if b { Some(i) } else { None })
        .sum::<usize>();

    println!("{}", sum_primes);
    println!("{} ms", now.elapsed().as_millis());

    let iter_now = Instant::now();
    let prime_iter = create_prime_iter(MAXNUM);
    let sum = prime_iter.sum::<usize>() + 2 + 3;

    sum_primes = 2;
    sum_primes += (sum..)
        .step_by(2)
        .zip(candidates.iter().skip((curr_prime + 1) / 2 - 1))
        .filter_map(|(i, b)| if b { Some(i) } else { None })
        .sum::<usize>();

    println!("{}", sum_primes);
    println!("{} ms", iter_now.elapsed().as_millis());
}


pub struct PrimeIter {
    curr_prime: usize,
    candidates: BitVec,
    maxnum    : usize,
}

impl Iterator for PrimeIter {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {

        if (self.curr_prime as f64) > (self.maxnum as f64).sqrt() {
            return None;
        }

        if (self.curr_prime as f64) < (self.maxnum as f64).sqrt() {
            ((self.curr_prime * self.curr_prime - 1) / 2..self.candidates.len())
            .step_by(self.curr_prime)
            .for_each(|x| self.candidates.set(x, false));

        }

        self.curr_prime += self.candidates
            .iter()
            .skip((self.curr_prime + 1) / 2)
            .position(|x| x)
            .unwrap()
            * 2
            + 2;
        Some(self.curr_prime)
    }
}

pub fn create_prime_iter(maxnum: usize) -> PrimeIter {
    let mut newiter = PrimeIter {
        curr_prime: 3,
        candidates: BitVec::from_elem(maxnum / 2, true),
        maxnum: maxnum,
    };

    newiter.candidates.set(0, false);
    newiter
}