Problem

Given a non-negative number n, we need to check if the number is a Prime number or not.

Examples:

Solution

fn is_prime(n: u32) -> bool {
    match n {
        _ if n <= 1 => return false,     // prime num has to be > 1
        _ if n == 2 => return true,      // 2 is prime num
        _ if n % 2 == 0 => return false, //other even nums could not be prime
        _ => (),
    }

    let sqrt_n = (n as f32).sqrt() as u32;

    // iterate over odd numbers i=3,5,7... while i <= sqrt(n)
    // if n is divisible by some i, then n is not prime num
    let mut i = 3;
    while i <= sqrt_n {
        if n % i == 0 {
            return false;
        }
        i += 2;
    }

    true
}

Explanation

First, we do several immediate checks to figure out if the number n is prime or not right away. As per the prime number definition, a prime number has to be >1. Also, an even number (except for 2) could not be a prime number because it would be always divisible by 2.

Then we iterate over odd numbers only i = 3, 5, 7... while i <= sqrt(n) and check if n is divisible by any i number. If that is the case, then the number n could not be prime. Note, that we could take a shortcut and iterate only up to sqrt(n) instead of doing it up to n. If the number is not prime, iterating till its square root should be enough to identify that, which saves us some execution time.

There are further ways how to optimize the performance of the Primality test. Those improvements take advantage of other observations of how prime numbers could be represented, which could make the computation even more efficient (e.g. less i numbers could be checked when iterating up to sqrt(n)). But we will leave out those further optimizations for this puzzle.

Complexity

The time complexity of the solution is O(sqrt(n)) (where n is the number we check for primality).

---

Rust Playground with this code