re: Project Euler #7 - 10001st prime VIEW POST

FULL DISCUSSION
 

Rust Solution: Playground

Got it to 17s, from 34s using the lazy iterators, was still using 2..(n/2) for checking primes.
Got it down to 0.9s by changing the prime check to 2..(sqrt(n)+1)

The iterator for checking prime uses any(|i| n % i == 0) instead of all(|i| !n % i == 0), so that it may short-circuit when any case returns true. Similar to using a loop with break condition.

Still is a brute force technique.


fn main() {
    println!("{}", get_nth_prime(10001));
}

fn get_nth_prime(n: usize) -> u32 {
    (1..).into_iter().filter(|&num| is_prime(num)).nth(n - 1).unwrap_or_default()
}

fn is_prime(n: u32) -> bool {
    match n {
        1 => false,
        2 => true,
        n if n % 2 == 0 => false,
        _ => !(2..(n as f32).sqrt() as u32 + 1).any(|i| n % i == 0),
    }
}
code of conduct - report abuse