# 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.

```.wp-block-code {
border: 0;
padding: 0;
-webkit-text-size-adjust: 100%;
text-size-adjust: 100%;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
padding: 0;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
padding-left: 0.75em;
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
padding: 0 0.75em;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```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.