lib.rs

#![feature(test)]

pub fn nth(index: usize) -> Result<usize, &'static str> {
    if index == 0 {
        return Err("index must be larger than 0");
    }

    let mut primes = vec![2usize];
    let mut number: usize = 3;

    // basic prime test: only check odd numbers, if that number is divisible
    // by any of the previously found primes, then we know it is not prime.
    // optimized by stopping when the current prime squared is larger than the number under test

    while primes.len() < index {
        if primes
            .iter()
            .filter(|&&x| x * x <= number)
            .all(|&x| number % x != 0)
        {
            primes.push(number);
        }
        number += 2;
    }

    Ok(primes[index - 1])
}

pub fn nth_loop(index: usize) -> Result<usize, &'static str> {
    if index == 0 {
        return Err("index must be larger than 0");
    }

    let mut primes = vec![2usize];
    let mut number: usize = 3;

    // basic prime test: only check odd numbers, if that number is divisible
    // by any of the previously found primes, then we know it is not prime.
    // optimized by stopping when the current prime squared is larger than the number under test

    while primes.len() < index {
        let mut is_prime = false;
        for prime in primes.iter() {
            if number % prime == 0 {
                break;
            }

            if prime * prime > number {
                is_prime = true;
                break;
            }
        }

        // make borrow checker happy
        if is_prime {
            primes.push(number);
        }
        number += 2;
    }

    Ok(primes[index - 1])
}


#[cfg(test)]
mod tests {
    extern crate test;
    use super::*;
    use self::test::Bencher;

    #[test]
    fn test_sixth_prime_iter() {
        assert_eq!(nth(6), Ok(13));
    }

    #[test]
    fn test_big_prime_iter() {
        assert_eq!(nth(10001), Ok(104743));
    }

    #[test]
    fn test_sixth_prime_loop() {
        assert_eq!(nth_loop(6), Ok(13));
    }

    #[test]
    fn test_big_prime_loop() {
        assert_eq!(nth_loop(10001), Ok(104743));
    }


    #[bench]
    fn bench_sixth_prime_iter(b: &mut Bencher) {
        b.iter(|| nth(6));
    }

    #[bench]
    fn bench_sixth_prime_loop(b: &mut Bencher) {
        b.iter(|| nth_loop(6));
    }

    #[bench]
    fn bench_large_prime_iter(b: &mut Bencher) {
        b.iter(|| nth(10001));
    }

    #[bench]
    fn bench_large_prime_loop(b: &mut Bencher) {
        b.iter(|| nth_loop(10001));
    }
}

/*
Results of: `rustup run nightly cargo bench`

test tests::bench_large_prime_iter ... bench:  28,416,092 ns/iter (+/- 1,034,377)
test tests::bench_large_prime_loop ... bench:   6,322,687 ns/iter (+/- 290,058)
test tests::bench_sixth_prime_iter ... bench:         374 ns/iter (+/- 54)
test tests::bench_sixth_prime_loop ... bench:         408 ns/iter (+/- 27)

*/