# Trial division

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