The best way to learn a language is to build stuff with it. So in that spirit, I’m working on a slightly bigger project for the next few days and will build it in parts. The first part is a function that checks if a number is prime, i.e. a primality test.

Definition

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

Examples

2, 3, 5, 7, 11, 43, 89, 479001599 etc.

Logic

To check if a number is prime we need to prove it is not composite. In other words, prove it has no divisors other than 1.

A brute force way would be to iterate each number less than it and check if any I is a divisor, i.e. n % i == 0, if it is the return false, else return true.

fn is_prime(n: u64) -> {
    for i in 1..n {
        if n % i == 0 {
            return false;
        }
    }
    true
}Code language: JavaScript (javascript)

This will take forever! Let’s improve it.

Logic 2.0

We know that there are no even prime numbers except for 2, so we can skip even numbers if we have a check that n is not 2. This improves it slightly, but we can do better.

In mathematics, we learn that any integer can be expressed in the form (6k + 1), where i is an element of [-1, 0, 1, 2, 3, 4] and k is any natural number greater than 0.

Using this knowledge we can significantly reduce the number of… well… numbers we need to check. when i is 0, 2, or 4 the result will always be even so we need not check those. And if we add a check for n % 3 == 0, we eliminate all multiples of 3.

We also do not need to check every number less than n, we only need to check up to the square root of n because Maths. Now we iterate from 0 to the square root of n and only check 6k ±1.

But wait aren’t we missing 4? No, because it’s even and we eliminated it. How about 2 and 3? We have checks for those. The final code looks like this:

Solution

pub fn is_prime(number: i64) -> bool {
    if number <= 3 {
        return number > 1;
    }
    if number % 2 == 0 || number % 3 == 0 {
        return false;
    }
    let upper_limit = (number as f64).sqrt().floor() as i64;
    for i in (5..=upper_limit).step_by(6){
        if number % i == 0 || number % (i + 2) == 0 {
            return false;
        }
    }
    true
}
Code language: Rust (rust)

Much faster. You can check the code and some tests in a gist, and if you have the time to waste, use it to check if 10888869450418352160768000001 is prime. Be warned it will take a while, but not as long as the brute force way.

That’s what I have for today. As I said in the beginning, this is just the first part of the larger project. I won’t be revealing what I’m building just yet. But some of you might be able to guess based on the next couple of tasks I will do. If you have a guess or suggestions for improvement of the code let me know on Twitter @phoexer, and happy coding.