If you're seeing this message, it means we're having trouble loading external resources for Khan Academy.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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