/* author Bill Wood */

fn sqrt(n: usize) -> usize {
    let (mut r1, mut r) = (n, n + 1);
    while r1 < r {
        r = r1;
        r1 = (r1 + n/r1) >> 1
    }
    r
}

struct Bvec {
    v: Vec<u8>
}
impl Bvec {
    fn new(val: bool, s: usize) -> Self {
        let valu8 = if val { 255 } else { 0 };
        Bvec { v: vec![valu8; (s >> 3) + if (s & 7) == 0 { 0 } else { 1 } ] }
    }
    #[inline(always)]
    fn get(&self, index: usize) -> bool {
        self.v[index >> 3] & 1 << (index & 7) != 0
    }
    #[inline(always)]
    fn _set(&mut self, mut index: usize, val: bool) {
        let bitpos = 1 << (index & 7);
        index >>= 3;
        if val {
            self.v[index] |= bitpos;
        } else {
            self.v[index] &= !bitpos;
        }
    }
    #[inline(always)]
    fn set_true(v: &mut [u8], mut index: usize) {
        let bitpos = 1 << (index & 7);
        index >>= 3;
        v[index] |= bitpos;
    }
}

struct SimpleSieve {
    primes: Vec<u32>,
}
impl SimpleSieve {
    fn new(high: usize) -> Self {
        assert_eq!(high | 1, high);
        let mut pvec = vec![false; (high + 1)/2];
        let mut primes = vec![];
        let n = high >> 1;
        let mut i = 3;
        while i*i <= high {
            if !pvec[i >> 1] {
                primes.push(i as u32);
                let mut j = (i*i) >> 1;
                while j <= n {
                    pvec[j] = true;
                    j += i;
                }
            }
            i += 2;
        }
        i >>= 1;
        while i <= n {
            if !pvec[i] {
                primes.push(((i << 1) | 1) as u32);
            }
            i += 1;
        }
        //dbg!(primes.len());
        SimpleSieve { primes, }
    }
}

struct SieveSlice<'a> {
    low: usize,
    high: usize,
    bslice: &'a mut [u8],
}
impl<'a> SieveSlice<'a> {
    fn new(low: usize, high: usize, bslice: &'a mut [u8]) -> Self {
        // assert_eq!(low | 1, low);
        // assert_eq!(high | 1, high);
        SieveSlice { low, high, bslice }
    }
    fn find(&mut self, sieve: &SimpleSieve) {
        let low = self.low;
        let high = self.high;
        if low <= 1 {
            Bvec::set_true(self.bslice, 0);
        }

        let n = (high - low) >> 1;
        for i in 0..sieve.primes.len() {
            let p = sieve.primes[i] as usize;
            let mut j = p*p;
            if j > high {
                break;
            }
            if j < low {
                j += (low - 1 - j + p*2)/2/p*p*2;
            }
            j = (j - low) >> 1;
            while j <= n {
                Bvec::set_true(self.bslice, j);
                j += p;
            }
        }
    }
}

use rayon::prelude::*;
struct Primes {
    low: usize,
    high: usize,
    sieve_seg: Bvec,
    lookup_table: Vec<Vec<u8>>,
}
impl Primes {
    fn new(mut low: usize, mut high: usize, mut seg_size_kb: usize) -> Option<Self> {
        // lowest odd >= low
        low |= 1;
        if low > high {
            return None;
        }
        // highest odd <= high
        high = (high - 1) | 1;
        // x where x: odd and (x+2)^2 > high and x^2 < high
        let ss_high = (sqrt(high) - 1) | 1;

        let sieve = SimpleSieve::new(ss_high);
        let mut sieve_seg = Bvec::new(false, (high + 2 - low)/2);
        println!("prime sieve size in KB = {}", sieve_seg.v.len()/1024);

        seg_size_kb = seg_size_kb.next_power_of_two();
        // 1024kb, 8 bit bytes, track odds only
        let seg_nprimes = seg_size_kb*1024*8*2;

        let mut segments = vec!();
        let mut seg_low = low;
        //dbg!(low, ss_high, seg_low, high, seg_size_kb, seg_nprimes, );
        for bslice in sieve_seg.v.chunks_mut(seg_size_kb*1024) {
            let mut seg_high = seg_low + seg_nprimes - 2;
            if seg_high > high {
                seg_high = high;
            }
            segments.push(SieveSlice::new(seg_low, seg_high, bslice));
            seg_low += seg_nprimes;
        }
        //dbg!(segments[0].bslice.len(), segments.len());

        segments.par_iter_mut().for_each(|seg| seg.find(&sieve));
        Some(Primes { low, high, sieve_seg, lookup_table: Primes::lookup_table_gen() })
    }
    #[inline(always)]
    fn is_prime(&self, index: usize) -> bool {
        !self.sieve_seg.get((index - self.low) >> 1)
    }
    fn lookup_table_gen() -> Vec<Vec<u8>> {
        let mut t = vec![vec![]; 256];
        for i in 0..256 {
            for j in 0..8 {
                if !i & 1 << j != 0 {
                    t[i].push((2*j) as u8);
                }
            }
        }
        t
    }
}

struct PrimesIter<'a> {
    sieve_index: usize,
    base: usize,
    low: usize,
    high: usize,
    sieve: &'a [u8],
    lookup_table: &'a Vec<Vec<u8>>,
    lookup_table_cur: &'a Vec<u8>,
    lookup_table_cur_index: usize,
}
impl<'a> Iterator for PrimesIter<'a> {
    type Item = usize;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        while self.lookup_table_cur_index >= self.lookup_table_cur.len() {
            if self.sieve_index >= self.sieve.len() {
                return None;
            }
            self.lookup_table_cur = &self.lookup_table[self.sieve[self.sieve_index] as usize];
            self.lookup_table_cur_index = 0;
            self.base = self.sieve_index*16 + self.low;
            self.sieve_index += 1;
        }
        let prime = self.base + self.lookup_table_cur[self.lookup_table_cur_index] as usize;
        self.lookup_table_cur_index += 1;
        if prime <= self.high {
            Some(prime)
        } else {
            None
        }
    }
}
impl<'a> IntoIterator for &'a Primes {
    type Item = usize;
    type IntoIter = PrimesIter<'a>;
    fn into_iter(self) -> Self::IntoIter {
        PrimesIter { sieve_index: 0, base: 0, low: self.low, high: self.high, sieve: &self.sieve_seg.v,
            lookup_table: &self.lookup_table, lookup_table_cur: &self.lookup_table[0], lookup_table_cur_index: 8 }
    }
}
impl Primes {
    fn seg_into_iter(&self, sieve_low_index: usize, sieve_high_index: usize) -> PrimesIter {
        let mut high = sieve_high_index*16 + self.low;
        if high > self.high {
            high = self.high;
        }
        let low = sieve_low_index*16 + self.low;
        PrimesIter { sieve_index: sieve_low_index, base: 0, low: 0, high, sieve: &self.sieve_seg.v,
            lookup_table: &self.lookup_table, lookup_table_cur: &self.lookup_table[0], lookup_table_cur_index: 8 }
    }
}

use time::PreciseTime;
use std::io::Write;
fn main() {
    let mut args = std::env::args()
        .skip(1)
        .map(|a| a
            .split('_')
            .fold("".to_string(), |a, s| a + s)
            .parse::<usize>());

    if args.len() <= 3 {
        if let (Ok(low), Ok(high), Ok(seg_size_kb), ) = (
                args.next().unwrap_or(Ok(1_000_000_000)),
                args.next().unwrap_or(Ok(2_000_000_000)),
                args.next().unwrap_or(Ok(128)),) {
            println!("S11: Finding sexy primes with args {} {} {}", low, high, seg_size_kb, );
            let start = PreciseTime::now();
            if let Some(primes) = Primes::new(low, high + 6, seg_size_kb) {
                let end = PreciseTime::now();
                println!("done generating primes in {:.2} secs...", start.to(end).num_milliseconds() as f64 / 1000.0);
                let mut count = 0;
                let mut nprimes: usize = if high >= 2 && low <= 2 { /*print!("{} ", 2);*/ 1 } else { 0 };

        // let seg_size_kb = seg_size_kb.next_power_of_two();
        // // 1024kb, 8 bit bytes, track odds only
        // let seg_nprimes = seg_size_kb*1024*8*2;

        // let mut segments = vec!();
        // let mut seg_low = low;
        // for bslice in primes.sieve_seg.v.chunks_mut(seg_size_kb*1024) {
        //     let mut seg_high = seg_low + seg_nprimes - 2;
        //     if seg_high > high {
        //         seg_high = high;
        //     }
        //     segments.push(SieveSlice::new(seg_low, seg_high, bslice));
        //     seg_low += seg_nprimes;
        // }

        // segments.par_iter_mut().for_each(|seg| seg.find(&sieve));
        // Some(Primes { low, high, sieve_seg, lookup_table: Primes::lookup_table_gen() })

                for p in primes.into_iter() {
                    if p > primes.high - 6 {
                        break;
                    }
                    nprimes += 1;
                    // if p < 200 { print!("{} ", p); }
                    if primes.is_prime(p + 6) {
                        //println!("sexy: {}, {}", p, p + 6);
                        count += 1;
                    }
                }
                println!("\n{} of {} primes are sexy", count, nprimes);
                return;
            }
        }
    }

    writeln!(
        std::io::stderr(),
        "Usage: sexy_primes low high seg_size(kb)"
    ).unwrap();
    std::process::exit(1);
}