2018-2-18

Finding the 10001st prime with Rust

If a number N has a prime factor larger than the square root of N, then it also has a prime factor smaller than square root of N.

The seventh Project Euler problem - 10001st prime - is stated as follows. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

#![feature(iterator_step_by)]

fn is_prime(n: u64) -> bool {
    if n == 2 || n == 3 {
        return true;
    } else if (n < 2) || (n % 2 == 0) {
        return false;
    }
    let upper_limit = (n as f64).sqrt() as u64;
    (3..upper_limit + 1)
        .step_by(2)
        .find(|i| n % i == 0)
        .is_none()
}

fn main() {
    let n = 10_001;
    let mut primes = 0u64;
    let mut i = 0u64;

    while primes < n {
        i += 1;
        if is_prime(i) {
            primes += 1;
        }
    }

    println!("{} is prime number {}.", i, n);
}
Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.