Main content

## Computer science

### Unit 2: Lesson 6

Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# 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).## Want to join the conversation?

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

- a simple trial question and answer for someone without programming background?(2 votes)
- For the programming part of this, does anyone know how to ask for the square root of a number in processing.js(2 votes)
- 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)
- Here's a simple counter example:

10 is not a perfect square.

10 is not prime.

The square root of 10 is ~3.16

2 is a a divisor of 10

2 <= 3.16

If a number x is not prime we will, like above, find a divisor which is <= sqrt(x)(3 votes)

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

- It is possible code in Python on the scratchpad ?(0 votes)
- 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) - 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)
- yet is it possible?(1 vote)

- 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)- The sqrt(n) is the highest possible number to get the n through the multiplication.So there is no need to check after sqrt(n).

for example 49 can be achieved through 7*7 only hence there is no need to check after 7(1 vote)