## Lesson goal: Prime number test

Previous: Add fractions and reduce answer to lowest terms | Home | Next: The Fibonacci Sequence

A prime number is a number that is divisible only by 1 and itself. For example, 13 is prime since only 1 and 13 divide evenly into 13; 14 however is not prime since 1, 2, 7, and 14 divide evenly into it.

In this lesson, we'll write a function called prime to test if a number is prime. The function will return true if the number if prime, and false if the number is not prime. To keep things simple, we'll implement something related to the "naive" test described on Wikipedia (link).

We'll use these conditions to test for primality of a number, held in variable $n$:
• Know that $2$ is prime (and the only even prime number).
• If $n$ is even, then two will divide evenly into it, and we'll conclude that the number is not prime.
• We'll only test if odd numbers divide evenly into $n$, since even numbers will only divide evenly into $n$ is $n$ is also even, and we have the first bullet point already.
• We'll only test numbers from 3 up to $\sqrt{n}$ since if $n$ has other factors, one must be $< \sqrt{n}$.