# Day 9: Rust Primality Test

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.