use std::cmp::min;

fn basicSieve(bound: usize) -> Vec<usize> {
    let mut isPrime = vec![true; bound];
    let top = ((bound as f64).sqrt().ceil() as usize) + 1;
    assert!(top < isPrime.len());
    for i in 2..top {
        if isPrime[i] {
            let mut j = i*i;
            while j < bound {
                isPrime[j] = false;
                j += i;
            }
        }
    }
    let mut result = Vec::with_capacity(bound);
    for i in 2..bound {
        if isPrime[i] {
            result.push(i);
        }
    }
    debug_assert!(result.len() < bound);
    result.shrink_to_fit();
    result
}

fn segmentedSieve(bound: usize) -> Vec<usize> {
    let fbound = bound as f64;
    // Approximitely x/(log x - 1) primes below x
    let estimatedPrimes = (fbound/(fbound.log10() - 1.0)) as usize;
    let mut result = Vec::with_capacity(estimatedPrimes);
    let segmentSize = fbound.sqrt().ceil() as usize;
    let mut isPrime = vec![true; segmentSize];
    // Seed the initial primes
    let primes = basicSieve(segmentSize);
    result.extend_from_slice(&primes);
    let mut start = segmentSize;
    while start < bound {
        for i in 0..segmentSize {
            isPrime[i] = true;
        }
        let end = min(bound + 1, start + segmentSize);
        let size = end - start;
        assert!(size <= segmentSize);
        for prime in &primes {
            let lastPrime = (((start as f64) / (*prime as f64)).ceil() as usize) * prime;
            debug_assert!(lastPrime >= start);
            let mut i = lastPrime - start;
            while i < size {
                isPrime[i] = false;
                i += *prime;
            }
        }
        for i in 0..size {
            if isPrime[i] {
                result.push(start + i);
            }
        }
        start += segmentSize;
    }
    result
}

fn main() {
    println!("basicSieve(20): {:?}", basicSieve(20));
    println!("segmentedSieve(500): {:?}", segmentedSieve(500));
    assert_eq!(basicSieve(500), segmentedSieve(500));
    println!("Huzzah, len(segmentedSieve(500)): {}", segmentedSieve(500).len());
}