## Define the problem

We need to build a machine which can answer a simple yes/no question. Given an input integer n, is n prime?

Let's think about what would be inside this machine to make it work. Machines can only follow a **sequence of steps** based on some instructions, known as an **algorithm**. To warm up, let's find out what algorithm is __inside your brain__. Answer the following question:** is 49 prime?**

…

No? How did you do that? You likely **searched for a divisor** of 49 which is **greater than 1 and less than 49**. If you haven't memorized your multiplication tables then you'd naturally follow this sequence:

- Does
**2**divide 49? NO - Does
**3**divide 49? NO - Does
**4**divide 49? NO - Does
**5**divide 49? NO - Does
**6**divide 49? NO - Does
**7**divide 49?**YES**

We found a divisor of 49 (**7**) which is **proof that 49 is composite.**

## Building a wall

However what if I asked you if **2971215073 is prime?**

Are you still checking? After the first few thousand tests I still haven't found a divisor. The key question is, **when can we stop checking and prove that n is prime?** (let's call this our **wall**) As a starting point, we know **our wall must be n-1** (since n divides n). If we check up to **2971215072 **either __we find a divisor__ (which proves n is **composite**) OR __we don't__ (which proves n is **prime**).

## Building a better wall

This would work, but **can we move our wall to save time**? Remember, that we are actually searching for the **first **(or smallest)** divisor**. Sometimes the smallest divisor could be 2, though it could also be much larger. This brings us to the key question: **how large could the smallest divisor be? **

Remember that any composite integer n is build out of two or more primes n** = P * P …**

**P is largest** when n has **exactly two divisors** which are **equal to each other**. This is known as a **square number** such as 9 (9 = 3*3) or 49 (49 = 7*7). To capture this worst case scenario we simply build our wall at the square root of n!

**Convince yourself of this:** __if we don't find a divisor of n after checking up to square root of n, then n must be prime__. Try to prove this to yourself (a proof is at the bottom of this article)

## Trial division algorithm

**That's it,** we are ready to move on. First let's summarize our trial division algorithm in plain english:

- Accept some input integer n
- For
**each integer x**from {2 ... sqrt(n)} check if**x divides n** - If you found a divisor then
**n is composite**OR ELSE**n is prime**

If you have programming experience you should open a CS scratchpad and try and get this function working. If not, you can proceed to the next step where I have provided a **working version** for you to use as a starting point. (FYI It __is possible__ to do this lesson without doing any programming).