### Tutorial 2 – Prime Numbers

#### Introduction

Julia has a clean and easy to understand syntax, as well as a propensity for mathematical programming.

Say, for example, that you wanted to write a program that determines whether or not a given number is prime. We will implement a simple trial division algorithm in this example, and work through a couple of optimizations.

Trial division is the simplest method for finding prime numbers, albeit a computationally intensive task. Julia is purpose built for applications like this, since it is designed out of the box for parallelism. For example, many encryption techniques rely on prime factorization routines. They are designed in such a way that trial divisions are extremely costly. In such an example, Julia could be employed to run in distributed fashion, across an array of commodity hardware to decrypt encrypted data relatively quickly.

Problems like this were typically the domain of low-level compiled languages like C and C++. Julia brings the power and speed of these languages to a dynamic language. If that isn't enough of a reason to try Julia, it also has a pretty syntax, the ability to run in parallel, and a vast and growing library of mathematical and scientific computing constructs.

This tutorial will show you the basics of how to define functions, perform basic arithmetic, specify types, and create loops.

#### Getting Started

Let's begin by creating a new file in Julia Studio. If this is your first time creating a file, you can do this through the file menu, by going to File ▸ New File, or by clicking on the New File icon in the middle of the Welcome tab.

For this tutorial create a file called `main.jl`

. This file will be where we begin execution of your program.

#### Background

Trial division is the simplest method for finding prime numbers. The way it works is by dividing the number, N, by incrementally large odd numbers, checking to see if the remainder is 0 for each division. If we find a factor, then we know the number is composite. If we check all the way up to without finding a factor, we can safely assume the number is prime. This solution is non-optimal, but easy to grasp. Let's give it a go: open up main.jl from the file system pane if it's not open already. First, we will define a function, `is_prime`

# In main.jl function is_prime(n) # insert magic here end # Prints the output of our function, when called with 100 println(is_prime(100))

The code above defines a new function, `is_prime`

, that takes argument, `n`

, and does absolutely nothing. How exciting! The following line calls `is_prime`

for the number 100 and prints the result to the console.

#### A word on types

Types in Julia are optional, but it's a good idea to specify types when it makes sense. In this case, the definition of a prime number implies that only natural numbers can be prime. It makes sense here to type the argument, n, to be an Integer. Julia has a few different Integer types, but the one you will use most often is Int64, unless you have a 32 bit computer, in which case your system will use Int32 by default.

Typed arguments are designated by following the argument definition with two colons and a type, like so:

function is_prime(n::Int64) # insert magic here end println(is_prime(100))

Try running the program. You should get a blank output. Now change the input from 100, which is implictly an Integer, to 100.0, which forces Julia to treat it as a floating point number (Float64 or Float32, depending on your system). You should get the error, `no method is_prime(Float64,)`

That might seem counter-intutive. After all, the method *is* defined, just not for those argument types. Julia allows you to define the same function multiple times with different argument types, like so:

function is_prime(n::Int64) # insert magic here end function is_prime(n::Int32) # insert magic here end function is_prime(n::Float64) # insert magic here end

For more on types, check out the awesome documentation.

#### Conditionals

Let's cut to the chase and write some code. The first thing our function should do is check to see if the number is less than or equal to 3, since these numbers are always prime. We'll also check to see if n is divisible by 2, because that rules out half of all numbers instantly.

function is_prime(n::Int64) if n <= 3 return true end if n % 2 == 0 return false end return true end

The 5 lines of code above, do a couple of things. First, we check to see if n is less than or equal to 3. We also check to see if it's divisible by 2, using the modulus operator, `%`

. The modulus operator essentially gets the remainder of the division between its two arguments (you could also call it as a function like so: `%(n, 2)`

see ref).

If the `n % 2`

is zero we know that n is divisible by 2 and we can return false, safe in our conclusion that n is composite. If we fail to return false, then the function will continue to be evaluated until it reaches the end, where it returns true. We need to write the logic that tests all the other possible factors of n. For that, we'll need a loop.

#### Loops

Loops are very simple with Julia. There are just two kinds, for loops and while loops. In this case, we will use a while loop, counting up from 3 to in increments of 2, checking for divisibility at each iteration

function is_prime(n::Int64) if n <= 3 return true end if n % 2 == 0 return false end # initialize a counter variable i = 3 while i <= sqrt(n) if n % i == 0 return false end i += 2 end return true end

Try this now, it should work! Just use the `println`

function to display the output of `is_prime`

for various different numbers

#### Conclusion

So our code is working. There's one other thing we can do to clean things up. We check to see if n is divisible by a number in two places, and the code is repeated. Let's create a function, `is_divisible`

, so that we aren't repeating ourselves

# in main.jl function is_divisble(n, i) return n % i == 0 end

Notice how we don't specify types for the arguments? This is because I want this method to work for both floating point numbers and integers. Julia allows me to leave them out and the compiler will infer type automatically.

Now let's just call that method from `is_prime`

. Here is what the completed code looks like

# in main.jl function is_divisble(n, i) return n % i == 0 end function is_prime(n::Int64) if n <= 3 return true end if is_divisble(n, 2) return false end # initialize a counter variable i = 3 while i <= sqrt(n) if is_divisble(n, i) return false end i += 2 end return true end