If you're seeing this message, it means we're having trouble loading external resources on our website.

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

Main content

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 = 33) or 49 (49 = 77). 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).

Want to join the conversation?

  • blobby green style avatar for user Voey Joltage
    if i'm not mistaken, if n is not 2, it could be determined if n is even, in which case it is not prime, and the rest of the process could be avoided, similarly, were this not the case, and the process of trial divisions were continued, all even divisors could be discarded, likely halving the length of process, if i'm correct.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      You are correct.
      A fairly standard optimization is to:
      check divisibility by 2
      start trial division from 3, checking only odd numbers

      Often we take it on step further:
      -check divisibility by 2
      -check divisibility by 3
      -starting at k=1 check divisibility by 6k-1 and 6k+1
      then increment k by 1
      (Any integer in the form of 6k+2, 6k+4 is divisible by 2 so we don't need to check them,
      Any integer in the form 6k, 6k+3 is divisible by 3 so we don't need to check them,
      this leaves only integers in the form 6k+1 and 6k+5 to check. But 6(k+1)-1 is the same as 6k+5, So if we increment k and check 6k-1 we will be checking 6k+5 for the original k )
      (9 votes)
  • blobby green style avatar for user Afia Adjeiwaa
    a simple trial question and answer for someone without programming background?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • primosaur sapling style avatar for user m u
    For the programming part of this, does anyone know how to ask for the square root of a number in processing.js
    (2 votes)
    Default Khan Academy avatar avatar for user
  • hopper cool style avatar for user ???
    Because it says if we don't find a divisor of n after checking up to square root of n, then n must be prime, then doesn't that mean that every number which is not a perfect square is a prime?
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user virtimus
    I wonder if it would be feasible to make some kind of state machine for this using iterative algorithm (to be found) ?
    Generating factorisations of subsequent composite numbers seams to be quite regular :
    4=2*2
    6=3*2
    8=2*2*2
    9=3*3
    10=5*2
    12=3*2*2
    14=7*2
    15=5*3
    16=2*2*2*2
    18=3*3*2
    20=5*2*2
    21=7*3
    22=11*2
    24=3*2*2*2
    25=5*5
    26=13*2
    27=3*3*3
    28=7*2*2
    30=5*3*2

    Checking factorisation of "n" would be just geting already computed close factorised composite <n, generate subsequent factorisations (using the algorithm) until f >n and check if the number is one of generated ... if not - we have a prime.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • ohnoes default style avatar for user Leilani Dickson
    I'm not very good at math, this seems very complicated just by me reading this. Is there a more simpler way to solve the problems that could help me understand
    (1 vote)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Christina DeRyke
      Lets look at 26.

      The square root of 25 is 5, so the square roots of 26 is 5.09. That means that 5.09*5.09 is 26. If 26 is not a prime number, then each product will include at least one number up to 5.09.

      Since we are looking for whole numbers, we are interested in the integers 2, 3, 4, and 5.

      Divide the start number, 26, by each of the integers.

      26\5 Not an integer
      26/4 Not an integer
      26/3 Not an integer
      26/2=13

      Since the product of two integers, 2 and 13, is 26, 26 is not a prime number. If you still do not understand you will want to head over to the math section and put in serious work.
      (2 votes)
  • blobby green style avatar for user epardomartin
    It is possible code in Python on the scratchpad ?
    (0 votes)
    Default Khan Academy avatar avatar for user
  • male robot donald style avatar for user Nathaniel Coxhead
    Here's some "pseudo-code" for anybody who is a bit confused.
    To find if N is prime:

    Set a variable named index to 2.
    Set a variable named result to true.
    While index squared is less than or equal to N:
    If N is divisible by index:
    Set result to false.
    Change index by 1.
    If result is true, N is prime or less than 2.
    If result is false, N is composite.

    The reason you only need to check for factors less than or equal to the square root of N is because if you have a factor F that is greater than the square root of N, the factor you multiply with F to get N is less than the square root of N.
    (1 vote)
    Default Khan Academy avatar avatar for user
  • leafers seed style avatar for user pn.naoned
    Why not just stop the algorithm if the result of the square root of n is an integer ? It would make the algorithm work faster.
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Ay Lmaeo
    I understand the topic but im not sure about, For each integer x from {2 ... sqrt(n)} check if x divides n; how do we arrived at that if all number less then sqrt(n) is not divisible by sqrt(n) means that number is prime can anyone explain it me.
    Thanks for your time.
    (1 vote)
    Default Khan Academy avatar avatar for user