extern crate bit_vec; // 0.4.4
use bit_vec::BitVec;

fn main() {
    println!("{:?}", backwards_prime(99999000, 100000000));
}

fn backwards_prime(start: u64, stop: u64) -> Vec<u64> {
    fn backwards(mut n: u64) -> u64 {
        let mut r = 0;
        while n > 0 {
            r = r * 10 + n % 10;
            n /= 10;
        }
        r
    }

    let mut max = 100;
    while max < stop {
        max *= 10;
    }
    let (primes, sieve) = prime(max);

    let start = match primes.binary_search(&start) {
        Ok(i) => i,
        Err(i) => i,
    };
    let stop = match primes.binary_search(&stop) {
        Ok(i) => i + 1,
        Err(i) => i,
    };

    primes
        .iter()
        .filter(|&p| {
            let b = backwards(*p);
            b != *p && sieve.get(b as usize).unwrap()
        })
        .cloned()
        .collect()
}

fn prime(max: u64) -> (Vec<u64>, BitVec) {
    let mut primes = {
        let max = max as f64;
        let max = max / max.ln() * 1.1;
        Vec::with_capacity(max as usize)
    };

    let mut sieve = BitVec::from_elem(max as usize, true);
    sieve.set(0, false);
    sieve.set(1, false);

    for i in 2..max {
        if sieve.get(i as usize).unwrap() {
            primes.push(i)
        }
        for &p in primes.iter() {
            if p * i >= max {
                break;
            }
            sieve.set((p * i) as usize, false);
            if i % p == 0 {
                break;
            }
        }
    }

    (primes, sieve)
}